A permutation \(p\) of size \(n\) is an array such that every integer from \(1\) to \(n\) occurs exactly once in this array.
Let's call a permutation an almost identity permutation iff there exist at least \(n - k\) indices \(i (1 ≤ *i* ≤ n)\) such that \(p_i = i\).
Your task is to count the number of almost identity permutations for given numbers \(n\) and \(k\).
The first line contains two integers \(n\) and \(k\) \((4 ≤ n ≤ 1000, 1 ≤ k ≤ 4)\).
Print the number of almost identity permutations for given \(n\) and \(k\).
Input
4 1
Output
1
Input
4 2
Output
7
Input
5 3
Output
31
Input
5 4
Output
76
给出\(n\)的全排列,求有多少种排列,满足至少\(n-k\)个位置上的数和下标相同(下标从\(1\)开始)
因为\(1\leq k\leq 4\),所以可以将题意转换一下:在\(n\)的全排列中,找到\(k\)个数,数和下标的值全都不相等
我们可以从\(n\)个数中,随机选出\(k\)个数,让这\(k\)个数全都没有放在正确的位置上,选\(k\)个数,我们可以用组合数来求,然后用错排公式来求有多少个数没放在正确的位置上。
因为\(k\)只有四个值,直接计算错排公式的值即可
最后将\(1\)~\(k\)中的这些值加起来即可
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define ms(a,b) memset(a,b,sizeof(a))
const int inf=0x3f3f3f3f;
const ll INF=0x3f3f3f3f3f3f3f3f;
const int maxn=1e6+10;
const int mod=1e9+7;
const int maxm=1e3+10;
using namespace std;
ll C(int n,int m)
{
ll fenmu=1LL;
ll fenzi=1LL;
for(int i=1;i<=m;i++)
{
fenmu=1LL*fenmu*(n-i+1);
fenzi=1LL*fenzi*i;
}
return fenmu/fenzi;
}
int main(int argc, char const *argv[])
{
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
srand((unsigned int)time(NULL));
#endif
ios::sync_with_stdio(false);
cin.tie(0);
int n,k;
cin>>n>>k;
ll ans=0;
if(k>=1)
ans+=1;
if(k>=2)
ans+=(n*(n-1)/2);
if(k>=3)
ans+=2*C(n,3);
if(k>=4)
ans+=9*C(n,4);
cout<<ans<<endl;
#ifndef ONLINE_JUDGE
cerr<<"Time elapsed: "<<1.0*clock()/CLOCKS_PER_SEC<<" s."<<endl;
#endif
return 0;
}
手机扫一扫
移动阅读更方便
你可能感兴趣的文章