点击打开fzu2282
题意：n个巫师参加会议，每个人有一根属于自己的魔杖。有一个巫师想打乱原本魔杖的排列顺序，问至少有k个人拿对的打乱方法有多少种。
思路：
题目要求至少有K个人拿对那么就是说拿对的人可以为k,k+1,....n.例如n=5,k=3,那么可以有3,4,5个人拿对。
解决：
n根魔杖的所有排列方式为A(n,n),所以只需要用所有的减去1,2。。。k个人拿错的情况就可以了。至于为什么不累加从k个人排错到n，是因为n较大会超时（错了才知道）。
所以只需要累加1,2..k个人拿错的情况就行了。列如k个人拿错，首先需要从n个人中选出k个人去哪错，即C（n,k）,然后其他n-k个人排错，即乘错排数。所以k个人拿错的的结果为
C(n,k)*a[n-k].（0<=k<=n）
排列组合公式：
下面是代码，其中求组合数用了费小马定理把除法变成了相乘，优化了算法。
费小马定理：假如p是质数，且gcd(a,p)=1，那么 a(p-1)≡1（mod p），即：假如a是整数，p是质数，且a,p互质(即两者只有一个公约数1)，那么a的(p-1)次方除以p的余数恒等于1。因为a*a^-1=1=a^(p-1)%p,所以a^-1=a^(p-2)%p.
#include<stdio.h>
#include<iostream>
#include<cstring>
using namespace std;
#define ll long long
#define mod 1000000007
ll a[10005],b[10005];
void init()
{a[0] = 1;a[1] = 0;a[2] = 1;b[1] = 1;b[2] = 2;for (int i = 3; i <= 10000; i ++){a[i] = (((i - 1) % mod) * ((a[i - 2] + a[i - 1])) % mod) % mod;b[i] = ((b[i - 1] % mod) * (i % mod)) % mod;}}
ll qpow(ll a, ll x) ///快速幂
{ll res = 1;while(x){if (x & 1){res = (res * a) %mod;}a = (a * a) % mod;x >>= 1;}return res;
}ll C(ll n, ll k) ///求组合数模版
{if(n < k){return 0;}if(k > n - k){k = n - k;}ll a = 1, b = 1;for(int i = 0; i < k; i++){a = a * (n - i) % mod; ///n*(n-1)*(n-2).....*kb = b * (i + 1) % mod; ///1*2*...*k}return a * qpow(b, mod - 2) % mod; ///费小马定理
}
int main()
{int n,m;int t;scanf("%d",&t);init();while(t--){scanf("%d %d",&n,&m);ll sum=b[n];ll ans=0;for(int i=0;i<m;i++){ans=( (ans%mod) + ((C(n,i)*a[n-i])%mod) )%mod;}// cout<<ans<<endl;printf("%lld\n",(mod +(sum%mod)-(ans%mod) )%mod);}return 0;
}