[LibreOJ 2034][SDOI2016]排列计数

danihao123 posted @ 2018年4月11日 16:30 in 题解 with tags SDOI 二项式反演 loj , 10 阅读
转载请注明出处:http://danihao123.is-programmer.com/

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

考虑用\(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;
}

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter