danihao123's Blog

我这种池沼只会做水题陶冶身心了……

考虑用\(f_i\)表示长为\(i\)的完全错位全排列的个数，那么有\(i\)个错位的长度为\(n\)的全排列的数量就是\(\binom{n}{i} f_i\)。从这一点出发，可以得到一个式子（枚举错位的有几个）：

\[n! = \sum_{i = 0}^n \binom{n}{i} f_i\]

考虑使用二项式反演，得到：

\[
\begin{aligned}
f_n &= \sum_{i = 0}^n (-1)^{n - i}\binom{n}{i} i!\\
&= \sum_{i = 0}^n (-1)^{n - i}\frac{n!}{(n - i)!}\\
&= n!\sum_{i = 0}^n \frac{(-1)^{n - i}}{(n - i)!}\\
&= n!\sum_{i = 0}^n \frac{(-1)^i}{i!}
\end{aligned}
\]

后面的和式可以预处理，然后就做完啦~

代码：

#include <cstdio>
#include <cstring>
using ll = long long;
const ll ha = 1000000007LL;
inline ll pow_mod(const ll &a, ll b) {
  ll ans = 1LL, res = a;
  while(b) {
    if(1LL & b) ans = (ans * res) % ha;
    res = (res * res) % ha;
    b >>= 1;
  }
  return ans;
}
inline ll inv(ll x) {
  return pow_mod(x, ha - 2LL);
}

const int N = 1000000;
const int maxn = N + 5;
ll fac[maxn], f[maxn];
inline void process() {
  fac[0] = 1LL;
  for(int i = 1; i <= N; i ++) {
    fac[i] = (fac[i - 1] * (ll(i))) % ha;
  }
  for(int i = 0; i <= N; i ++) {
    f[i] = (i % 2 == 1) ? (ha - 1LL) : 1LL;
    f[i] = (f[i] * inv(fac[i])) % ha;
    if(i > 0) f[i] = (f[i - 1] + f[i]) % ha;
  }
}

int main() {
  process();
  int T; scanf("%d", &T);
  while(T --) {
    int n, m; scanf("%d%d", &n, &m);
    int p = n - m;
    ll bs = (fac[p] * f[p]) % ha;
    ll C = (fac[n] * inv((fac[p] * fac[m]) % ha)) % ha;
    printf("%lld\n", (bs * C) % ha);
  }
  return 0;
}