FZU 2282 Wand(错排公式)

Description:

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:

2 1 1 3 1

Sample Output:

1 4

题目链接

n个数1~n求 $i \in [k, n]$ 中i个数字在自己位置上的所有情况数量。

错排公式为n个数都不在自己位置上的所有可能情况数量，递推求得错排数Staggered[i]

$\sum_{i - k}^{n} C_{n}^{i} * S t a g g e r e d [n - i]$ 即为结果。

其中 $C_{n}^{i}$ 代表i个数在自己位置上的数量，Staggered[n-i]代表其余数都不在自己位置上的数量。

其中求 $C_{n}^{i}$ 要用到阶乘逆元，阶乘逆元递推中先通过飞马小定理利用快速幂求出一个最大值的阶乘逆元之后由大向小递推。

Staggered[0]要初始化为1,因为 $C_{n}^{i} * S t a g g e r e d [0]$ 为所有数都在自己位置上的数量，显然为1。

AC代码:

#include <iostream>
#include <cstdio>
using namespace std;

const int maxn = 1e4 + 5;
const int mod = 1e9 + 7;

long long Staggered[maxn];

void StaggeredInit() {
    Staggered[0] = 1;
    Staggered[1] = 0;
    Staggered[2] = 1;
    for (int i = 3; i < maxn; ++i) {
        Staggered[i] = (i - 1) * (Staggered[i - 1] + Staggered[i - 2]) % mod;
    }
}

long long QuickMul(long long A, long long B) {
    long long Res = 0;
    while (B) {
        if (B & 1) {
            Res = (Res + A) % mod;
        }
        A = (A + A) % mod;
        B >>= 1;
    }
    return Res;
}

long long QuickPow(long long A, long long B) {
    long long Res = 1;
    while (B) {
        if (B & 1) {
            Res = QuickMul(Res, A) % mod;
        }
        A = QuickMul(A, A) % mod;
        B >>= 1;
    }
    return Res;
}

long long Factorial[maxn], FactorialInv[maxn];

void FactorialInvInit() {
    Factorial[0] = 0;
    Factorial[1] = 1;
    for (int i = 2; i < maxn; ++i) {
        Factorial[i] = (Factorial[i - 1] * i) % mod;
    }
    FactorialInv[maxn - 1] = QuickPow(Factorial[maxn - 1], mod - 2);
    for (int i = maxn - 2; i >= 0; --i) {
        FactorialInv[i] = (FactorialInv[i + 1] * (i + 1)) % mod;
    }
}

int main(int argc, char *argv[]) {
    StaggeredInit();
    FactorialInvInit();
    int T;
    scanf("%d", &T);
    for (int Case = 1, N, K; Case <= T; ++Case) {
        scanf("%d%d", &N, &K);
        long long Ans = 0;
        for (int i = K; i <= N; ++i) {
            Ans = (Ans + (((Factorial[N] * FactorialInv[i]) % mod * FactorialInv[N - i]) % mod * Staggered[N - i]) % mod) % mod;
        }
        printf("%lld\n", Ans);
    }
    return 0;
}