专栏文章

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

llittlebug
P4071题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@min0qkq6
此快照首次捕获于
2025/12/01 18:40
3 个月前
此快照最后确认于
2025/12/01 18:40
3 个月前
查看原文
组合意义天地灭，代数推导保平安。
二项式反演板子。怎么能么没有反演的题解呢！
注意到题目要求「恰好 mm 个」，所以考虑二项式反演。
令 fmf_m 为恰好 mm 个 ai=ia_i = i 的方案数，gmg_m 为钦定 mm 个 ai=ia_i = i 的方案数，则根据二项式反演可知：
fm=∑i=mn(−1)i−m(im)gif_m = \sum _{i=m} ^n (-1)^{i-m} \binom i m g_i
然后求 gmg_m，考虑从 nn 个位置中钦定 mm 个满足 ai=ia_i = i，剩下的随便排列，有：
gm=(nm)(n−m)!g_m = \binom n m (n-m)!
把两个式子放到一起：
fm=∑i=mn(−1)i−m(im)(ni)(n−i)!f_m = \sum _{i=m} ^n (-1)^{i-m} \binom i m \binom n i (n-i)!
把组合数拆成阶乘形式，可以得到：
fm=∑i=mn(−1)i−mi!m!(i−m)!n!i!(n−i)!(n−i)!=∑i=mn(−1)i−mn!m!(i−m)!=n!m!∑i=mn(−1)i−m1(i−m)!=n!m!∑i=0n−m(−1)i1i!\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)O(n+T)。
CPP
// === / 走吧 就算我们无法让大雨停下 还有我 陪你在雨里放肆奔跑啊 / ===

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]);
}
华风夏韵，洛水天依！

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...