聰聰考試，我是證人聰聰
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
