K - Wand FZU - 2282 【 组合数 + 错排 】

K - Wand

FZU - 2282 

N wizards are attending a meeting. Everyone has his own magic wand. N magic wands was put in a line, numbered from 1 to n(Wand_i owned by wizard_i). After the meeting, n wizards will take a wand one by one in the order of 1 to n. A boring wizard decided to reorder the wands. He is wondering how many ways to reorder the wands so that at least k wizards can get his own wand.

For example, n=3. Initially, the wands are w1 w2 w3. After reordering, the wands become w2 w1 w3. So, wizard 1 will take w2, wizard 2 will take w1, wizard 3 will take w3, only wizard 3 get his own wand.

Input

First line contains an integer T (1 ≤ T ≤ 10), represents there are T test cases.

For each test case: Two number n and k.

1<=n <=10000.1<=k<=100. k<=n.

Output

For each test case, output the answer mod 1000000007(10^9 7).

Sample Input

代码语言：javascript复制

2
1 1
3 1

Sample Output

代码语言：javascript复制

1
4

&：求 n 个人中至少有 k 个人拿对了自己的东西。 &：对应的是有最多有 n-k 个人拿错了，所以记有 i 个人拿错的种类是 f [ i ] ，那么只需要从 n 中挑选出 i 个人，累加一下就可以了，因为组合数和错排数都会很大，这里要用到取模以及逆元。

代码语言：javascript复制

#include<iostream>
#include<map>
#include<cstdio>
using namespace std;
# define ll long long
# define inf 0x3f3f3f3f
const ll mod =  1e9 7;
const ll maxn = 2e5 100;
ll f[maxn];  // 错排
ll inv[maxn];  //存逆元
ll A[maxn];     //Amn 
ll Pow(ll x, ll n)  // 快速幂求逆元
{
    ll ans = 1;
    while(n)
    {
        if(n&1)
            ans *= x, ans %= mod;
        x = x * x;
        x %= mod;
        n >>= 1;
    }
    return ans;
}
void Init() // 求逆元
{
    A[1] = inv[1] = 1;
    ll ans = 1;
    ll n = 200002 100;
    for(ll i = 2; i < n; i   )
    {
        ans =ans*i;
        ans %= mod;
        A[i] = ans;
        inv[i] = Pow(ans,mod-2);
    }
}
ll C(ll n, ll m)  // 组合数 Cmn
{
    if(m == n || m == 0)
        return 1;
    return A[n]*inv[n-m]%mod*inv[m]%mod;
}
void init() // 错排公式
{
    f[1]=0ll,f[2]=1ll;
    for(ll i=3; i<=10002; i  )
    {
        f[i]=((i-1 mod)%mod*(f[i-1] f[i-2] mod)%mod mod)%mod;
    }
}
int main()
{
    ios::sync_with_stdio(false);
    init();
    Init();
    ll  T;
    cin>>T;
    while(T--)
    {
        ll n,m;
        cin>>n>>m;
        ll ans=1ll;
            for(ll  i=2; i<=n-m; i  ) 
            {
                ans= (ans C(n,i)%mod * f[i]%mod)%mod;
            }
            ans%=mod;
        cout<<ans<<endl;
    }
    return 0;
}

case input line sample wizard

0 人点赞