傳送門

題意 ： 給你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 错排的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。