省选前最后水一发…

SDOI 好像很喜欢数学题？_(:_」∠)_

用 $f(n)$ 表示 $1 \sim n$ 的错排方案数（满足 $A_i \neq i, \forall i$ 的排列数），容易看出 $Ans = f(n-m) \binom{n}{m}$。

其中有 $f(n) = \sum_{i=0}^{n} (-1)^i \binom{n}{i} (n-i)!$。具体证明可以 Orz vfk

接下来是喜闻乐见的化简时间

\[\begin{align}
Ans & = f(n-m) \binom{n}{m} \\
 & = \sum_{i=0}^{n-m} (-1)^i \binom{n-m}{i} (n-m-i)! \cdot \binom{n}{m} \\
 & = \sum_{i=0}^{n-m} (-1)^i \frac{(n-m)!}{i! (n-m-i)!} \cdot (n-m-i)! \cdot \frac{n!}{m! (n-m)!} \\
 & = \sum_{i=0}^{n-m} (-1)^i \frac{n!}{m! \cdot i!} \\
 & = \frac{n!}{m!} \cdot \sum_{i=0}^{n-m} \frac{(-1)^i}{i!}
\end{align}\]

惊奇地发现（一点也不）所有的阶乘以及除法逆元都可以 $O(n \log n)$ 预处理（不会 $O(n)$ _(:_」∠)_）。。然后又惊奇地发现 $\sum_{i=0}^{n-m} \frac{(-1)^i}{i!}$ 可以通过 $O(n)$ 预处理计算部分和。。于是变成了 $O(n \log n)-O(1)$ 目测 60s 不会被卡常数？= =

然后就愉快地解决了（难得不靠找规律做出一道数学题 QwQ）时间复杂度 $O(n \log n + t)$

/**************************************************************
    Problem: 4517
    User: cyand1317
    Language: C
    Result: Accepted
    Time:31724 ms
    Memory:24192 kb
****************************************************************/

#include <stdio.h>
#define MAXN 1000004
#define MODULUS 1000000007
typedef long long int64;
 
int n, m;
 
// f(n) = # of permutations P of length n
//        where not exists such i that P[i] = i
// F(n) = sigma[i = 0 to n] f(i) * C(n,i)
//      = n!
 
// Binomial inversion
// f(n) = sigma[i = 0 to n] (-1)^i * C(n,i) * (n-i)!
// Ans = f(n-m) * C(n,m)
//     = sigma[i = 0 to n-m] (-1)^i * C(n-m,i) * (n-m-i)! * C(n,m)
 
// C(n,m) * C(n-m,i) * (n-m-i)!
// = n!/(m! (n-m)!) * (n-m)!/(i! (n-m-i)!) * (n-m-i)!
// = n!/(m! i! (n-m-i)!) * (n-m-i)!
// = n!/(m! i!)
// Ans = (sigma[i = 0 to n-m] (-1)^i / i!) * n!/m!
 
int64 fact[MAXN], fact_inv[MAXN], pfxsum[MAXN];
int64 fpow(int64 base, int exp)
{
    int64 ans = 1;
    while (exp) {
        if (exp & 1) ans = ans * base % MODULUS;
        base = base * base % MODULUS;
        exp >>= 1;
    }
    return ans;
}
void preprocess()
{
    int i;
    fact[0] = fact[1] = 1;
    fact_inv[0] = fact_inv[1] = 1;
    pfxsum[0] = 1; pfxsum[1] = 0;
    for (i = 2; i < MAXN; ++i) {
        fact[i] = fact[i - 1] * i % MODULUS;
        fact_inv[i] = fpow(fact[i], MODULUS - 2);
        if (i & 1) pfxsum[i] = (pfxsum[i - 1] - fact_inv[i] + MODULUS) % MODULUS;
        else pfxsum[i] = (pfxsum[i - 1] + fact_inv[i]) % MODULUS;
    }
}
int64 nCr(int n, int m)
{
    return (fact[n] * fact_inv[m]) % MODULUS * fact_inv[n - m] % MODULUS;
}
int64 calc(int n, int m)
{
    return n < m ? 0 : pfxsum[n - m] * fact[n] % MODULUS * fact_inv[m] % MODULUS;
}
 
int main()
{
    preprocess();
    int t; scanf("%d", &t);
    do {
        scanf("%d%d", &n, &m);
        printf("%lld\n", calc(n, m));
    } while (--t);
    return 0;
}

貌似 $O(n \log n)$ 跑得挺慢的？= =

之前 WA 了一发。。原因是计算部分和的时候没有 mod MODULUS。。（果然还是弱 省选药丸药丸啊←_←）

总之省选加油  Ganbarimasu~