| 聪聪考试 |
| 难度级别：C； 运行时间限制：1000ms； 运行空间限制：262144KB； 代码长度限制：2000000B |
|
试题描述
|
|
聪聪是一个善良可爱、睿智聪慧的好孩子。聪聪是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。 |
题解：
n个人当中有k个人拿到的一定不是自己的作业，我们只需要考虑k个人没有拿到自己作业的情况，所以我们可以先来一个dp数组储存到k的全错排列。动规方程是：dp[i]=(i-1)*dp[i-1]+(i-1)*dp[i-2](dp[i]代表i个人，全部拿到的不是自己作业的种类数)。
动规方程来源：
有一种情况是：假如当前有i个人，我们可以假设前i-1个人拿到的全都不是自己的作业，那么第i个人拿到的一定是自己的作业，所以我们可以让第i个人的作业与前i-1任意一个人的作业进行交换，就是(i-1)dp[i-1]。
还有一种情况：就是假设前i-1个人中有1个人拿到自己的作业，也就是说第i个人一定要与拿到自己的作业的人的作业进行交换，这样算出来就是(i-1)dp[i-2]。
以上两种情况构成了所有的情况，所以我们可以得到dp方程：dp[i]=(i-1)*dp[i-1]+(i-1)*dp[i-2]
我们需要从n个人中选取k个人拿到的不是自己的作业，对于每一次选取，都有dp[k]种情况，所以最后答案是dp[k]*C(n,k)。
但是由于数据比较大，在处理C(n,k)的时候应该用卢卡斯定理。
以下是代码：
1 #include<iostream> 2 #define MAXN 1000000+10 3 using namespace std; 4 const int mod=10007; 5 int qp_mod(int x,int n){ 6 int b=1; 7 while(n>0){ 8 if(n&1)b=b*x%mod; 9 x=x*x%mod; 10 n>>=1; 11 } 12 return b; 13 } 14 int comb(int n,int m){ 15 if(m>n)return 0; 16 if(m==n)return 1; 17 int M=1; 18 for(int i=1;i<=m;i++){ 19 i%=mod; 20 M=M*i%mod; 21 } 22 M=qp_mod(M,mod-2); 23 for(int i=n;i>=n-m+1;i--){ 24 i%=mod; 25 M=M*i%mod; 26 } 27 return M; 28 } 29 int Lucas(int n,int m){ 30 int ans=1; 31 while(n&&m&&ans){ 32 ans=ans*comb(n%mod,m%mod)%mod; 33 n/=mod;m/=mod; 34 } 35 return ans; 36 } 37 int n,k; 38 int dp[MAXN]; 39 int main(){ 40 scanf("%d%d",&n,&k); 41 if(k==0){ 42 cout<<1; 43 return 0; 44 } 45 dp[1]=0;dp[2]=1; 46 for(int i=3;i<=k;i++){ 47 dp[i]=(i-1)%mod*((dp[i-1]+dp[i-2])%mod)%mod; 48 } 49 cout<<Lucas(n,k)*dp[k]%mod; 50 }