罗老师想给N个集训队员每人一张卡片,开片上事先写好了名字。到发的那天,就只有K个集训队员到场,罗老师有点生气,就随便给他们每人发了一张,但突然想起来名字已经写好了,很可能发错了,甚至每个人发到的都不是自己应该拿的卡片。
罗老师灵机一动,问大家,N张中选K张,每个人都拿错的发法有几种,答案很大,结果取余1,000,000,007。
输入N和K
输出多少种方法
2 1
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)个人错排
将1和2的方式加起来就是答案了。