FZU 2282 错排

传送门

题意 ： 给你n个人, k 个数, 任意交换n个人的顺序，1号还在一号位就表示它的位置是对的. 则问你至少k个人还在对的位置的方案有几种. 

思路：这明显是排列组合问题。先把所有的情况求出来A(n,n)也就是n！减去错排的情况。具体就是定某些位置不动，其他位置进行错排。

C(i,n)*D(n-i)。

#include <bits/stdc++.h> #define LL long long using namespace std; const int mod=1e9+7; const int maxn=1e4+7; LL D[maxn], C[maxn][105]; int p[1000050]; void init() {D[0]=1;D[1]=0;for(int i=1;i<maxn;i++)//错排D[i]=((i-1)*(D[i-1]+D[i-2])+mod)%mod;int i;for (p[0]=i=1;i<=200000;i++) p[i]=1ll*p[i-1]*i%mod;for (int i = 0; i < maxn; i++)//排列组合{for (int j = 0; j <= min(105, i); j++){if (j == 0) C[i][j] = 1;elseC[i][j] = (C[i-1][j] + C[i-1][j-1]) % mod;}} } int main() {init();int t;cin>>t;while(t--){int n,k;cin>>n>>k;LL ans=1;for(LL i=1;i<=n;i++)ans = ans * i % mod;LL val=0;for(int i=0;i<k;i++)val=(val+D[n-i]*C[n][i]) % mod;cout<<(ans-val+mod) % mod<<endl;} }

总结

以上是生活随笔为你收集整理的FZU 2282 错排的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。