2016.1.26試題描述聰聰是一個善良可愛、睿智聰慧的好孩子。聰聰是100%的學霸，這一天她在考數學。聰聰很快做到了最後一道題：“高一八班有n個人，從1到n編號，一次互判作業時，老師隨機將作業發到這n個人手中。已知有k個人拿到的不是自己的作業，那麼請問有多少種情況符合條件呢？”這麼簡單的問題聰聰當...
2016.1.26
| 試題描述 |
|
聰聰是一個善良可愛、睿智聰慧的好孩子。聰聰是100%的學霸，這一天她在考數學。聰聰很快做到了最後一道題：“高一八班有n個人，從1到n編號，一次互判作業時，老師隨機將作業發到這n個人手中。已知有k個人拿到的不是自己的作業，那麼請問有多少種情況符合條件呢？”這麼簡單的問題聰聰當然會做了，她想考考你，你能不能比她先給出問題的答案呢? |
| 輸入 |
| 共1行，包含2個整數n和k。 |
| 輸出 |
| 共1行，包含1個整數，表示答案。由於答案可能很大，請輸出答案模10007的餘數。 |
| 輸入示例 |
| 4 3 |
| 輸出示例 |
| 8 |
| 其他說明 |
|
對於30%的數據，0≤k≤n≤10。 另有10%的數據，k=0。 另有10%的數據，k=1。 對於70%的數據，0≤k≤n≤10000。 對於100%的數據，0≤k≤1000000，1≤n≤1000000000。 |
C(n,k)*f[k],其中f[k]表示全錯排列第k項。
關鍵是組合數取模！
在函數C中若b>a則直接返回0！（因為這是定義）
把我坑了半天！
所以得出一個很牛x的結論！
C(a,b)模p不等於0的充要條件是a在p進位下的每一位都不小於b在p進位下對應的位，C(a,b)模p等於0的充要條件是a在p進位下至少有一位小於b在p進位下對應的位！
或者上面那句話不好理解的話也沒關係，反正沒什麼卵用，寫代碼的時候不要忘了判定就好。
AC代碼：
#include<iostream> using namespace std; const int mod=10007; int n,k,f[1000005]; int ans=1; int qpow(int a,int b) { int ret=1; while(b) { if(b&1) (ret*=a)%=mod; b/=2; (a*=a)%=mod; } return ret; } int C(int a,int b) { if(b>a) return 0; if(a-b<b) b=a-b; int s1=1,s2=1; for(int i=1;i<=b;i++) { (s1*=i)%=mod; (s2*=(a-i+1))%=mod; } return (s2*qpow(s1,mod-2))%mod; } void Lucas(int a,int b) { if(!a||!b) return ; Lucas(a/mod,b/mod); (ans*=C(a%mod,b%mod))%=mod; } int main() { scanf("%d%d",&n,&k); Lucas(n,k); f[0]=f[2]=1; for(int i=3;i<=k;i++) { f[i]=( ((i-1)%mod) * ((f[i-1]+f[i-2])%mod) )%mod; } if(k>n) cout<<0; else printf("%d",ans*f[k]%mod); }View Code
