反演板子怎么能没有反演题解 || solution - P4071

· · 题解

组合意义天地灭，代数推导保平安。

二项式反演板子。怎么能么没有反演的题解呢！

注意到题目要求「恰好 m 个」，所以考虑二项式反演。

令 f_m 为恰好 m 个 a_i = i 的方案数，g_m 为钦定 m 个 a_i = i 的方案数，则根据二项式反演可知：

f_m = \sum _{i=m} ^n (-1)^{i-m} \binom i m g_i

然后求 g_m，考虑从 n 个位置中钦定 m 个满足 a_i = i，剩下的随便排列，有：

g_m = \binom n m (n-m)!

把两个式子放到一起：

f_m = \sum _{i=m} ^n (-1)^{i-m} \binom i m \binom n i (n-i)!

把组合数拆成阶乘形式，可以得到：

\begin{aligned} f_m & = \sum _{i=m} ^n (-1)^{i-m} \frac {i!} {m! (i-m)!} \frac {n!} {i! (n-i)!} (n-i)! \\ & = \sum _{i=m} ^n (-1)^{i-m} \frac {n!} {m! (i-m)!} \\ & = \frac {n!} {m!} \sum _{i=m} ^n (-1)^{i-m} \frac 1 {(i-m)!} \\ & = \frac {n!} {m!} \sum _{i=0} ^{n-m} (-1)^i \frac 1 {i!} \end{aligned}

然后发现后面那个求和就可以直接预处理一个前缀和来做了。

时间复杂度 O(n+T)。

// === / 走吧 就算我们无法让大雨停下 还有我 陪你在雨里放肆奔跑啊 / ===

int n,m,fac[N],finv[N],s[N];

il void solve()
{
    read(n,m);
    write(mod_(mod_(fac[n]*finv[m])*s[n-m]),'\n');
}

il void init()
{
    finv[0]=finv[1]=fac[0]=fac[1]=1;
    rep(i,2,N) finv[i]=mod_((mod-mod/i)*finv[mod%i]);
    rep(i,2,N) fac[i]=mod_(fac[i-1]*i),finv[i]=mod_(finv[i-1]*finv[i]);
    s[0]=1; rep(i,1,N-1) s[i]=mod_(s[i-1]+(i&1?-1:1)*finv[i]);
}

华风夏韵，洛水天依！