XTU

admin管理员组

文章数量:1794759

XTU

大家可以点赞、评论，如果讲解的不够详细或者看不懂的都可以留言。多给我些反馈，可以让我更好的编写博客内容。

题目描述

快递小哥每天都辛苦的送快递，今天他需要送N份快递给N个收件人，第i份快递需要送给第i个收件人。 请问其中发生恰好K个送错了的情况数是多少？

输入

存在多样例。 每行输入两个整数N和K，1≤N≤1000,0≤K≤N。 如果两个都为0，则表示输入结束，这个样例不需要处理。

输出

每行输出一个样例的结果，因为数值会比较大，所有结果需要对109+7取模。

样例输入

1 1
2 1
3 2
1000 1000
0 0

样例输出

0
0
3
37043040

解题思路：错排+组合数+模运算

这题题目有对结果取模的运算，涉及到一个模运算，内容比较多，大家自行查找学习，CSDN就有很多。 然后，本题考察的就是排列组合问题【（进阶版？）离散数学里的知识点】，所以大家一定要认真学习啊，不要觉得上课的知识用不上。 

组合数 ：组合数很简单 就是 n个里面取k个人 C(n,k)。这里我选用杨辉三角写，用公式算太麻烦了。

错排： k个人里面怎么分配送错的快递。（csdn也有很详细的解释）

然后这个题就出来了。（注意爆int）

AC代码：

#include <stdio.h>const int Mod = 1e9+7, N = 1003;
int i,j,n,k;
__int64 D[N],YHtriangle[N][N];void Print()
{for ( i = 0; i < N; i ++)                          // 杨辉三角YHtriangle[i][0] = YHtriangle[i][i] = 1;for ( i = 2; i < N; i ++)for ( j = 1; j < i; j ++)YHtriangle[i][j] = (YHtriangle[i-1][j-1]+YHtriangle[i-1][j]) % Mod;D[2] = 1;                                          // 错排  for ( i = 3; i < N; i ++)D[i] = (i-1) * (D[i-1]+D[i-2]) % Mod;
}int main()
{Print();while ( scanf("%d %d",&n,&k) != EOF && !(n==0 && k==0)){if (k == 0)     puts("1");else            printf("%I64d\n",YHtriangle[n][k]*D[k]%Mod);}return 0;
}

本文标签： XTU