问题1017--卡片

1017: 卡片

时间限制: 1 Sec  内存限制: 128 MB
提交: 25  解决: 19
[提交] [状态] [讨论版] [命题人:]

题目描述

罗老师想给N个集训队员每人一张卡片,开片上事先写好了名字。到发的那天,就只有K个集训队员到场,罗老师有点生气,就随便给他们每人发了一张,但突然想起来名字已经写好了,很可能发错了,甚至每个人发到的都不是自己应该拿的卡片。

罗老师灵机一动,问大家,N张中选K张,每个人都拿错的发法有几种,答案很大,结果取余1,000,000,007

输入

输入NK

输出

输出多少种方法

样例输入 Copy

2 1

样例输出 Copy

1

提示

【样例说明】

其他样例

输入

3 1

输出

4

 

输入

3 3

输出

2

 

输入

7 4

输出

2790

 

输入

9 1

输出

322560

 

输入

714 9

输出

466134693

【数据规模和约定】

N的范围(1<=N<=1000)

K的范围(1<=K<=12)

K<=N



题解:

可以使用错排公式加组合公式

错排公式:

n个编号元素放在n个编号位置,元素编号与位置编号各不对应的方法数用D(n)表示,那么D(n-1)就表示n-1个编号元素放在n-1个编号位置,各不对应的方法数,其它类推.

第一步,把第n个元素放在一个位置,比如位置k,一共有n-1种方法;

第二步,放编号为k的元素,这时有两种情况:把它放到位置n,那么,对于剩下的n-1个元素,由于第k个元素放到了位置n,剩下n-2个元素就有D(n-2)种方法;k个元素不把它放到位置n,这时,对于这n-1个元素,有D(n-1)种方法;

综上得到

D(n) = (n-1) [D(n-2) + D(n-1)]

特殊地,D(1) = 0, D(2) = 1.

 

组合公式:

c(n,m)=c(n-1,m-1)+c(n-1,m)

 

N个中取K张使得这K个人都不正确

可以枚举 1. K个人错排

         2. 剩下的人中取(1 <= i <=N-k)人,然后(K+i)个人错排

12的方式加起来就是答案了。

来源/分类