「学习笔记」各类容斥反演总结

一点乱记，用于个人理解和巩固，亦可作为一篇学习顺序参考的文章。

如有笔误敬请指出。

二项式反演

组合恒等式

$\binom{n}{k}=\binom{n}{n-k},n\geq 0$，对称恒等式。

$k\binom{n}{k}=n\binom{n-1}{k-1},k\neq 0$，吸收恒等式。

$\binom{n}{m}\binom{m}{k}=\binom{n}{k}\binom{n-k}{m-k}$，组合意义易证。

$\sum_k \binom{r}{m+k}\binom{s}{n-k}=\binom{r+s}{n+m}$，范德蒙德卷积，组合意义易证。

求一列的前缀和：$\sum_i\binom{i}{m}=\binom{n+1}{m+1}$，放在杨辉三角上易解释。

更多的可以去看具体数学（？）

例题一 ARC016F Card Game for Three

小 A，小 B，小 C 在玩游戏。他们每个人分别有 $n,m,k$ 张牌，每张牌上面写着 $a,b,c$ 三个字母中的其中一个，每个回合有一个人出牌，如果出牌为 $a$ 则小 A 下一个回合出牌，如果出牌为 $b$ 则小 B 下一个回合出牌，小 C 同理。若轮到某位玩家出牌时，其手中无牌，则该位玩家获胜。

现在小 A 第一个出牌，对所有 $3^{n+m+k}$ 种手牌拥有的可能性计算小 A 获胜的方案数，对 $10^9+7$ 取模。

如果按照打出的顺序排成一个长度为 $l$ 的序列，小 A 获胜当且仅当：$a$ 恰好出现了 $n$ 次且在最后一次出现，$b$ 出现了不多于 $m$ 次，$c$ 出现了不多于 $k$ 次。

而这个长度为 $l$ 的序列对应了 $3^{n+m+k-l}$ 种手牌拥有的情况。

$n$ 次是一定打的，枚举 $b,c$ 出现的次数 $t$，然后枚举 $b$ 出现的次数 $i$：

$$\sum_{t=0}^{m+k}\binom{n+t-1}{n-1}3^{m+k-t}\sum_{i=t-k}^{m}\binom{t}{i}$$

第一个组合数是除了最后一个是 $a$，确定 $(n-1)$ 个 $a$ 的位置，$3^{m+k-t}$ 是计算的对应了多少种手牌拥有情况，最后一个组合数为在 $t$ 个 $b,c$ 都可以填的空位挑出 $i$ 个填 $b$，注意这个组合数可能会出现 $i<0$ 或 $i>t$ 的情况，由于是考虑其实际的组合意义，所以当出现这样的情况时视为 $0$．

最后一个实际上是组合数一行的区间和，众所周知这个的计算是困难的，由于这个区间和的形式比较特殊，考虑递推出这个东西：

$$\begin{aligned} S(t)=&\sum_{i=t-k}^{m}\binom{t}{i} \\ =&\sum_{i=t-k}^{m}\binom{t-1}{i-1}+\sum_{i=t-k}^{m}\binom{t-1}{i} \\ =&\sum_{i=t-k-1}^{m-1}\binom{t-1}{i}+\sum_{i=t-k}^{m}\binom{t-1}{i} \\ =&\ 2\cdot\sum_{i=t-k-1}^{m}\binom{t-1}{i}-\binom{t-1}{m}-\binom{t-1}{t-k-1} \\ =&\ 2\cdot S(t-1)-\binom{t-1}{m}-\binom{t-1}{t-k-1} \end{aligned}$$

至此，可以在 $\mathcal{O}(n+\log \bmod)$ 的时间复杂度内解决问题。

Code

二项式反演

形式一：

$$f(n)=\sum_k(-1)^k\binom{n}{k}g(k)\Longleftrightarrow g(n)=\sum_k(-1)^k\binom{n}{k}f(k)$$

形式二（至多和恰好的转换）：

$$\begin{aligned} f(n)=\sum_k \binom{n}{k}g(k)\Longleftrightarrow g(n)=\sum_k(-1)^{n-k}\binom{n}{k} f(k) \end{aligned}$$

形式三（至少和恰好的转换）：

$$f(n)=\sum_k\binom{k}{n}g(k)\Longleftrightarrow g(n)=\sum_k (-1)^{k-n}\binom{k}{n}f(k)$$

三种形式的证明类似，可以看 vfk 的PPT。

要区分这里的“至多,至少”和前缀和/后缀和对应的“至多至少”，二项式反演的“至多,至少”实际上是钦点一部分满足条件，其余部分随意，而前缀和/后缀和的“至多,至少”是钦点一部分满足条件之后，其他的必须不满足，所以前者是带一个二项式系数的。

例题二 BZOJ 3622 已经没有什么好害怕的了

先各自排下序，$k\gets \frac{n+k}{2}$，其含义为要恰好有 $k$ 对满足 $a>b$．

直接 dp 不太好做，因为如果状态设置为”前 $i$ 个 $a$ 匹配了 $j$ 对 $a>b$” 的话，我们要考虑 $b$ 中小于 $a_i$ 的个数 $l_i$ 中有多少个数被之前选过了，然而只从 $j$ 这一维无法体现这个信息。

所以就钦点 $j$ 这一维表示 $l_i$ 中有多少个 $b$ 被之前的 $a$ 选过了，只让 $a$ 和小于它的 $b$ 匹配，最后剩下的就让他们乱排，乘一个阶乘。由于最后乱排还可能匹配出 $ab$．

设 $F(k)$ 为至少有 $k$ 对 $a>b$，$G(k)$ 为恰好有 $k$ 对 $a>b$．

$F$ 很容易 dp 出来，也就是：

$$F(k)=f_{n,k}(n-k)!$$

其中 $f_{i,j}=f_{i-1,j}+f_{i-1,j-1}(l_i-j+1)$，分别表示 $a_i$ 进行匹配而是鸽到最后再匹配 和 $a_i$ 找一个比它小的 $b$ 匹配。

考虑到：

$$F(k)=\sum_i\binom{i}{k}G(i)$$

很好理解，就是考虑这个“至少”的方案实际上有多少对 $a>b$．

二项式反演得：

$$G(k)=\sum_i(-1)^{i-k}\binom{i}{k}F(i)$$

问题解决。

莫比乌斯反演

欧拉函数

• $\varphi(p^k)=(p-1)p^{k-1}$
• $\varphi(n)=n\prod (1-\frac{1}{p})$，既可以从容斥原理角度考虑，也可以考虑直接利用 $\varphi$ 为积性函数拆开对于每个素因子单独计算。

常用狄利克雷卷积

• $1\ast\mu=\epsilon \Rightarrow\sum\limits_{d|n}\mu(d)=[n==1]$，考虑 $\mu(d)\neq 0$ 的 $d$，按照素因子个数分类在一起，再枚举素因子个数然后二项式定理；
• $id=\varphi\ast 1\Rightarrow id\ast\mu=\varphi$，考虑对 $\leq n$ 且与 $n$ 的 $\gcd$ 为 $d$ 的正整数个数为 $\varphi(\frac{n}{d})$；

狄利克雷前缀和/差分/后缀和/差分

感性理解一下，实际上问题就是关于质因数分解后指数的高维前缀和。

前缀和实际上是卷了一个 $1$，这个很好理解，因为式子一模一样。

前缀差分实际上是卷了一个 $\mu$，因为 $b=a\ast\mu \Longleftrightarrow a=b\ast 1$，而已知 $a$ 求 $b$ 实际上就是狄利克雷前缀差分。

狄利克雷前缀和

for(int i = 1; i <= pct; ++i)
	for(int j = 1; j*p[i] <= n; ++j)
		a[j*p[i]] += a[j];

狄利克雷前缀差分

for(int i = 1; i <= pct; ++i)
	for(int j = n/p[i]; j; --j)
		a[j*p[i]] -= a[j];

狄利克雷后缀和

for(int i = 1; i <= pct; ++i)
	for(int j = n/p[i]; j; --j)
		a[j] += a[j*p[i]];

狄利克雷后缀差分

for(re int i = 1; i <= pct; ++i)
	for(re int j = 1; j <= n/p[i]; ++j)
		a[j] -= a[j*p[i]];

更一般的，如果对于任意的积性函数，也有类似的方法。

设数论函数为 $F$，积性函数为 $G$，欲求 $F\ast G$．

先把 $F$ 拆分成若干之和质数 $p$ 有关的积性函数 $F_p$ 的卷积，即：

$$F_p(n)\left\{\begin{matrix} F(n)&n=p^k \\ 0&\mathrm{otherwise} \end{matrix}\right.$$

显然有 $F=\prod F_p$．

把这些 $F_p$ 分别卷到 $G$ 上去即可求得答案。

$$(G\ast F_p)(n)=\sum_{p^k|n}G(\frac{n}{p^k})F_p(p^k)$$

对于每个 $p^k$ 枚举其倍数然后计算，预先存下需要用到的 $G$ 即可。

这样复杂度为 $\mathcal{O}(\sum n/p^k)$，等比数列求和可得 $\mathcal{O}(\sum n/p^k)=\mathcal{O}(n\sum \frac{1}{p-1})=\mathcal{O}(n\log \log n)$．

例子 $\gcd$ 卷积

求 $c_n=\sum\limits_{(i,j)=n}a_ib_j$ ．

莫比乌斯反演易做到 $\mathcal{O}(n\log n)$（？）这里可以用狄利克雷前缀和做到 $\mathcal{O}(n\log \log n)$．

先求 $c$ 的高维后缀和 ${c’}_{n}=\sum\limits_{n|(i,j)}a_ib_j$ 再狄利克雷后缀差分即可求得答案。

$$\begin{aligned} {c'}_n&=\sum_{n|(i,j)}a_ib_j \\ &=\sum_{n|i,n|j}a_ib_j \\ &=\sum_{n|i}a_i\sum_{n|j}b_j \\ &={a'}_n{b'}_n \end{aligned}$$

所以，将 $a,b$ 作高维后缀和（狄利克雷后缀和），点乘后作高维后缀差分即可得到 $c$．

莫比乌斯反演

设 $g(n)$ 为数论函数。

如果 $f$ 为 $g$ 的狄利克雷前缀和即：

$$f(n)=\sum_{d|n}g(d)\tag{1}$$

则有：

$$g(n)=\sum_{d|n}\mu(\frac{n}{d})f(d)\tag{2}$$ $$g=f\ast\mu$$

证明： $f=g\ast1 \Rightarrow f\ast\mu=(g\ast 1)\ast\mu=g\ast(1\ast\mu)=g\ast\epsilon=g$．

另一种形式：

如果有：

$$f(n)=\sum_{n|d}g(d)$$

则有：

$$g(n)=\sum_{n|d}\mu(\frac{d}{n})f(d)$$

这里的 $d$ 通常是小于等于一个界限，也就是题目中所给定的 “$n$”。

特别地，当 $n=1$ 时，$g(1)=\sum \mu(d)f(d)$，也可以理解为容斥系数为 $\mu$ 的容斥。

证明可以看 oi-wiki（

设 $F(n)=\exp(f(n)),G(n)=\exp(g(n))$ 对 $(1)$ 式 $\exp$，得到：

$$F(n)=\prod_{d|n}G(d)$$

对 $(2)$ 式 $\exp$，得到：

$$G(n)=\prod_{d|n}F(d)^{\mu(\frac{n}{d})}$$

也就是：

$$f(n)=\prod_{d|n}g(d)\Longleftrightarrow g(n)=\prod_{d|n}f(d)^{\mu(\frac{n}{d})}$$

知道应该怎么推，避免遇到有 $\prod$ 的数论题直接抓瞎（

例题一

求长度为 $n$ 且仅包含小写英文字母且循环节长度恰为 $n$ 的字符串的个数。

$n\leq 10^9$．

设 $f(n)$ 为长度为 $n$ 的字符串个数，$g(n)$ 为长度为 $n$ 且最小循环节长度为 $n$ 的字符串个数。

$f(n)$ 是易求的，其为 $26^n$．我们可以枚举最小循环节，用 $g$ 来算出 $f$：

$$f(n)=\sum_{d|n}g(d)$$

莫比乌斯反演得：

$$g(n)=\sum_{d|n}\mu(\frac{n}{d})f(d)$$

轻易解决。

例题二 Codeforces 1559E Mocha and Stars

对第三个条件进行莫比乌斯反演，得：

$$ans=\sum_{d=1}^m \mu(d)f(d)$$

其中 $f(d)$ 为 $\gcd$ 为 $d$ 的倍数时的答案。

对于 $f(d)$，每次可以做一下背包，用前缀和优化易做到 $\mathcal{O}(\frac{nm}{d})$，总时间复杂度就是 $\mathcal{O}(nm\log nm)$，注意到 $\mu(d)$ 为 $0$ 的时候不用跑背包，所以这个远远跑不满。

Code

斯特林反演

第一类斯特林数

$s(n,k)$ 为把 $n$ 个数分成 $k$ 个无区分轮换的方案数，也可以表示为 $\begin{bmatrix}n\\k\end{bmatrix}$。

特别地：

• $\begin{bmatrix}n\\0\end{bmatrix}=0,n>0$；
• $\begin{bmatrix}0\\0\end{bmatrix}=1$：我们假装只有一种方法可以把一个空集钦点成零个非空轮换。

第一类斯特林数有递推式：

$$\begin{bmatrix}n\\k\end{bmatrix}=\begin{bmatrix}n-1\\k-1\end{bmatrix}+(n-1)\begin{bmatrix}n-1\\k\end{bmatrix}$$

考虑组合意义，$n$ 是单独一个轮换还是和前面分在一起。

$$\begin{bmatrix}n\\k\end{bmatrix}=\sum_{i=1}^n \binom{n-1}{i-1}(i-1)!\begin{bmatrix}n-i\\k-1\end{bmatrix}$$

考虑组合意义，$1$ 所在的轮换的大小是 $i$．

第一类斯特林数 · 行

设 $G_n(x)=\sum_i \begin{bmatrix}n\\i\end{bmatrix}x^i$，则根据递推式有 $G_n=xG_{n-1}+(n-1)G_{n-1}=(x+n-1)G+{n-1}$，展开之后得到：

$$G_n(x)=\prod_{i=0}^{n-1}(x+i)=x^{\overline n}$$

显然可以分治 + FFT 在 $\mathcal{O}(n\log^2 n)$ 来求得 $G_n$，也可以倍增 + FFT：

假设现在已经求出了 $G_n(x)=\sum a_ix^i$，想要求得 $G_{2n}(x)$：

$$\begin{aligned} G_{2n}(x)=G_n(x)\times G_n(x+n) \\ G_n(x+n)&=\sum_i a_i(x+n)^i \\ &=\sum_i a_i\sum_{j} \binom{i}{j}x^jn^{i-j} \\ &=\sum_i{x^i}\frac{1}{i!}\sum_{j} a_jj!\frac{n^{j-i}}{(j-i)!} \end{aligned}$$

这样两次卷积就能求出 $G_{2n}(x)$，复杂度为 $T(n)=T(n/2)+\mathcal{O}(n\log n)=\mathcal{O}(n\log n)$．

多项式技巧不精，第一类斯特林数 · 列待填坑。

第二类斯特林数

$S(n,k)$ 为把 $n$ 个数分成 $k$ 个无区分集合的方案数，也可以表示为 $\begin{Bmatrix}n\\k\end{Bmatrix}$．

特别地：

• $\begin{Bmatrix}n\\0\end{Bmatrix}=0,n>0$；
• $\begin{Bmatrix}0\\0\end{Bmatrix}=1$：我们假装只有一种方法可以把一个空集钦点成零个非空部分。

第二类斯特林数有递推式：

$$\begin{Bmatrix}n\\k\end{Bmatrix}=\begin{Bmatrix}n-1\\k-1\end{Bmatrix}+k\begin{Bmatrix}n-1\\k\end{Bmatrix}$$

考虑组合意义即可，$n$ 是单独一个集合还是分在前面的集合中。

$$\begin{Bmatrix}n\\k\end{Bmatrix}=\sum_{i=1}^n \begin{Bmatrix}n-i\\k-1\end{Bmatrix}\binom{n-1}{i-1}$$

考虑组合意义即可，$i$ 为枚举的 $1$ 所在的集合大小是多少。

第二类斯特林数通项 / 第二类斯特林数 · 行

有一个恒等式：

$$m^n=\sum_{i=0}^{m}m^{\underline i}\begin{Bmatrix}n\\i\end{Bmatrix}=\sum_{i=0}^m\binom{m}{i}\begin{Bmatrix}n\\i\end{Bmatrix}i!$$

考虑组合意义即可，左边是 $n$ 个球放入 $m$ 个可空盒子的方案数，右边是枚举非空的集合数，亦可以用数学归纳法证明。

二项式反演得：

$$\begin{Bmatrix}n\\m\end{Bmatrix}m!=\sum_{i=0}^m(-1)^{m-i}\binom{m}{i}i^n$$

进一步转化可得：

$$\begin{Bmatrix}n\\m\end{Bmatrix}=\sum_{i=0}^{m} \frac{(-1)^{i}}{i !} \cdot \frac{(m-i)^{n}}{(m-i) !}$$

这样就化成了一个卷积的形式，可以 $\mathcal{O}(n\log n)$ 求得所有的 $\begin{Bmatrix}n\\i\end{Bmatrix}$．

多项式技巧不精，第二类斯特林数 · 列待填坑。

上降幂与普通幂

在 “一行第一类斯特林数求和” 中提到过上升幂转普通幂：

$$x^{\overline n}=\sum_{k=0}^n \begin{bmatrix}n\\k\end{bmatrix}x^k\tag{1}$$

另有普通幂转上升幂：

$$x^n=\sum_{k=0}^n\begin{Bmatrix}n\\k\end{Bmatrix}(-1)^{n-k}x^{\overline{k}}\tag{2}$$

数学归纳法易证。

下降幂与普通幂

在 “第二类斯特林数通项 / 一行第二类斯特林数求和” 中提到过普通幂转下降幂：

$$x^n=\sum_{k=0}^{n}\begin{Bmatrix}n\\k\end{Bmatrix}x^{\underline k}\tag{3}$$

另有下降幂转上升幂：

$$x^{\underline n}=\sum_{k=0}^n\begin{bmatrix}n\\k\end{bmatrix}(-1)^{n-k}x^k\tag{4}$$

数学归纳法易证。

不用数学归纳法？显然有 $x^{\underline n}=(-1)^n (-x)^{\overline n}$（直接拆开易证），代入到 $(3)$ 得 $(2)$，代入到 $(2)$ 得 $(4)$．

反转公式

将 $(4)$ 代入到 $(3)$ 得：

$$\begin{aligned} x^n&=\sum_{i=0}^{n}\begin{Bmatrix}n\\k\end{Bmatrix}\sum_{m=0}^k\begin{bmatrix}k\\m\end{bmatrix}(-1)^{k-m}x^m \\ &=\sum_{m=0}^nx^m\sum_{k=m}^n\begin{Bmatrix}n\\k\end{Bmatrix}\begin{bmatrix}k\\m\end{bmatrix}(-1)^{k-m} \end{aligned}$$

对比系数可得：

$$\sum_{k=m}^n\begin{Bmatrix}n\\k\end{Bmatrix}\begin{bmatrix}k\\m\end{bmatrix}(-1)^{k-m}=[m=n]\tag{5}$$

同理，把 $(1)$ 代入 $(2)$ 可得：

$$\\ \sum_{k=m}^n\begin{Bmatrix}n\\k\end{Bmatrix}\begin{bmatrix}k\\m\end{bmatrix}(-1)^{n-k}=[m=n]\tag{6}$$

把 $(2)$ 代入 $(1)$ 得：

$$\sum_{k=m}^n\begin{bmatrix}n\\k\end{bmatrix}\begin{Bmatrix}k\\m\end{Bmatrix}(-1)^{k-m}=[m=n]\tag{7}$$

把 $(3)$ 代入 $(4)$ 得：

$$\sum_{k=m}^n\begin{bmatrix}n\\k\end{bmatrix}\begin{Bmatrix}k\\m\end{Bmatrix}(-1)^{n-k}=[m=n]\tag{8}$$

有的地方将 $(5),(7)$ 称为反转公式，有的地方将 $(6),(8)$ 称为反转公式，在此并不继续深究。

斯特林反演

$$f(n)=\sum_{k=0}^n\begin{Bmatrix}n\\k\end{Bmatrix}g(k)\Longleftrightarrow g(n)=\sum_{k=0}^n(-1)^{n-k}\begin{bmatrix}n\\k\end{bmatrix}f(k)\tag{9}$$ $$f(n)=\sum_{k=0}^n\begin{bmatrix}n\\k\end{bmatrix}g(k)\Longleftrightarrow g(n)=\sum_{k=0}^n(-1)^{n-k}\begin{Bmatrix}n\\k\end{Bmatrix}f(k)\tag{10}$$

证明一下 $(9)$：

$$\begin{aligned} g(n)&=\sum_{i=0}^n[n=i]g(i) \\ &=\sum_{i=0}^n\sum_{k=i}^n\begin{bmatrix}n\\k\end{bmatrix}\begin{Bmatrix}k\\i\end{Bmatrix}(-1)^{n-k}g(i) \\ &=\sum_{k=0}^n(-1)^{n-k}\begin{bmatrix}n\\k\end{bmatrix}\sum_{i=0}^k\begin{Bmatrix}k\\i\end{Bmatrix}g(i) \\ &=\sum_{k=0}^n(-1)^{n-k}\begin{bmatrix}n\\k\end{bmatrix}f(k) \end{aligned}$$

$(10)$ 的证明类似，证明思路大概是：找到一个 “$if$”，说一句废话，把式子代入，交换求和号，整理一下。

通过前面二项式反演的证明以及后面提到的反演的证明更加体现了这个思路。

前面证莫比乌斯反演也是可以这么证的，不过用狄利克雷卷积更简单我就用狄利克雷卷积证了。

例题一 HDU 4372 Count the Buildings

$n$ 前面有 $F-1$ 个前缀最大，$n$ 后面有 $B-1$ 个后缀最大，那么把每一个前/后缀最大及其前/后面一段没有碰到前/后缀最大的看成一段，发现是钦定这一段让最大值排最前面，所以这些方案数是 $\begin{bmatrix}n-1\\F+B-2\end{bmatrix}$，然后选出 $F-1$ 个放在 $n$ 前面，答案为 $\binom{F+B-2}{F-1}\begin{bmatrix}n-1\\F+B-2\end{bmatrix}$．

例题二 HDU 7095 / 2021 年百度之星·程序设计大赛 - 复赛 B Add or Multiply 1

你有一个数字 $x$ 和若干个操作，每个操作是 $+a_i$ 或者乘 $\times a_i$ 中的一种。你可以重新排列这些操作的顺序，然后对数字 $x$ 执行这些操作。

比如说三个操作是 $+a_1,+a_2,\times a_3$。如果按顺序执行这三个操作，那么得到的结果是 $((x+a_1)+a_2)\times a3$。如果排列成 $+a_2,\times a_3,+a_1$，那么得到的结果是 $((x+a_2)\times a_3)+a_1$。

我们会发现，有一些操作顺序计算出来的结果是本质相同的，比如说 $+a_1,+a_2,\times a_3$ 和 $+a_2,+a_1,\times a_3 $这样运算下来结果是一样的。我们认为两个操作顺序计算的结果本质相同，当且仅当无论代入什么数，计算出来的结果都是一样的。

请问有多少种本质不同的操作序列。换句话说就是最多能找到多少个操作序列，使得这些操作序列任意两个都不是本质相同的。由于答案很大，输出对 $10^9+7$ 取模的结果。

在这个题目中，我们只会给出加法操作和乘法操作的个数，分别是 $n,m$，并不会给出具体的顺序和数字。容易发现，答案与具体的顺序和数字无关。

共 $T$ 组询问，$1\leq T\leq 10^4,1\leq n,m\leq 3000$．

把 $x$ 个有标号球放进 $y$ 个有区分非空盒子方案数 $= y!\times$ 把 $x$ 个有标号球放进 $y$ 个无区分非空盒子方案数 $= \begin{Bmatrix}x\\y\end{Bmatrix}y!$，设其为 $calc(x,y)$．

其中 $\begin{Bmatrix}x\\y\end{Bmatrix}$ 为第二类斯特林数。

考虑枚举有 $i$ 个连起来的乘法块，那么其方案数为 $calc(m,i)$．

$i$ 个乘法块形成了 $(i+1)$ 个空隙，两边的 $2$ 个可空，中间的 $(m-1)$ 个非空。

$n$ 个加法有三种方法：

1. 只放中间 $(m-1)$ 个（钦点两个可空的都不放）：$calc(n,i-1)$；

2. 钦点一个可空的为非空的，另一个不放：$calc(n,i)\times 2$；

3. 钦点两个可空的为非空的：$calc(n,i+1)$．

故答案为

$$\sum_{i=1}^mcalc(m,i)\times(calc(n,i-1)+calc(n,i-1)\times 2+calc(n,i+1))$$

时间复杂度为 $\mathcal{O}(m^2+Tm)$．

Code

例题三 「TJOI / HEOI2016」求和

求：

$$f(n)=\sum_{i=0}^n\sum_{j=0}^i\begin{Bmatrix}i\\j\end{Bmatrix}2^jj!\bmod998244353$$

$1\leq n\leq 10^5$

第二类斯特林数看起来就不好处理，考虑用第二类斯特林数通项公式把 $\begin{Bmatrix}i\\j\end{Bmatrix}j!$ 换掉：

$$\begin{aligned} &=\sum_{i=0}^n\sum_{j=0}^i\begin{Bmatrix}i\\j\end{Bmatrix}2^jj! \\ &=\sum_{i=0}^n\sum_{j=0}^i2^j\sum_{k=0}^j(-1)^{j-k}\binom{j}{k}k^i \\ &=\sum_{j=0}^n\sum_{k=0}^j2^j(-1)^{j-k}\binom{j}{k}\sum_{i=j}^nk^i \\ &=\sum_{j=0}^n\sum_{k=0}^j2^j(-1)^{j-k}\frac{j!}{k!(j-k)!}\cdot\frac{k^{n+1}-1}{k-1} \end{aligned}$$

注意最后一步等比数列求和当 $k=0,1$ 的时候需要特判掉。

把仅关于 $j$ 的提出来，仅关于 $k$ 的合并，仅关于 $(j-k)$ 的合并，整理成卷积的形式：

$$\begin{aligned} &=\sum_{j=0}^n2^jj!\sum_{k=0}^j\frac{(-1)^{j-k}}{(j-k)!}\cdot\frac{k^{n+1}-1}{k!(k-1)} \end{aligned}$$

快乐 FFT，复杂度 $\mathcal{O}(n\log n)$．

例题四 TopCoder 13444 CountTables

设 $g(m)$ 为 $n$ 行 $m$ 列的矩阵，满足任意两行不相同的方案数，则有 $g(m)=c^m(c^m-1)(c^m-2)…=(c^m)^{\underline n}$．

设 $f(m)$ 为 $n$ 行 $m$ 列的矩阵，满足任意两行两列都不相同的方案数，则有：

$$g(m)=\sum_{i=0}^m\begin{Bmatrix}m\\i\end{Bmatrix}f(i)$$

也就是划分成 $i$ 个集合，每个集合里面都用一样的列。

斯特林反演一下得到：

$$f(m)=\sum_{i=0}^m(-1)^{m-i}\begin{bmatrix}m\\i\end{bmatrix}g(i)$$

例题五 Crash 的文明世界

给定 $n$ 个点边权均为 $1$ 的树和非负整数 $m$，对于每个点 $i$ 求出：

$$\sum_{j=0}^n\text{dist}(i,j)^m$$

对 $10^4+7$ 取模。

$n\leq 5\times 10^4,m\leq 150$

暴力 点分治+FFT 可以做到 $\mathcal{O}(n\log^2n)$？

考虑普通幂转下降幂：

$$\begin{aligned} &\sum_{j=0}^n\text{dist}(i,j)^m \\ =&\sum_{j=0}^n\sum_{k=0}^{\text{dist}(i,j)}\binom{\text{dist}(i,j)}{k}\begin{Bmatrix}m\\k\end{Bmatrix}k! \\ =&\sum_{j=0}^n\sum_{k=0}^{m}\binom{\text{dist}(i,j)}{k}\begin{Bmatrix}m\\k\end{Bmatrix}k! \\ =&\sum_{k=0}^{m}\begin{Bmatrix}m\\k\end{Bmatrix}k!\sum_{j=0}^n\binom{\text{dist}(i,j)}{k} \end{aligned}$$

设 $\sum\limits_{j=0}^n\binom{\text{dist}(i,j)}{k}=f_{i,k}$，如果能对于每个 $i$ 求得 $f_{i,k}$ 即可求得答案。

考虑固定 $i$ 为根，此时的 $j$ 的取值仅能为子树内点的编号。

$$\begin{aligned} f_{x,k}&=\sum_{v\in son(x)}\sum_{w\in subtree(v)}\binom{\text{dist}(v,w)+1}{k} \\ &=\sum_{v\in son(x)}\sum_{w\in subtree(v)}\binom{\text{dist}(v,w)}{k-1}+\sum_{v\in son(x)}^n\sum_{w\in subtree(v)}\binom{\text{dist}(v,w)}{k} \\ &=\sum_{v\in son(x)}f_{v,k-1}+f_{v,k} \end{aligned}$$

此时只有根的答案是正确的，再换根 dp 即可。

时间复杂度 $\mathcal{O}(nm)$．

Code

子集反演

$$f(S)=\sum_{T\subseteq S}g(T)\Longleftrightarrow g(S)=\sum_{T\subseteq S}(-1)^{|S|-|T|}f(T)$$

众所周知，子集和超集本质上是相同的，只需要把每个集合看成自己的补集即可，同样有：

$$f(S)=\sum_{S\subseteq T}g(T)\Longleftrightarrow g(S)=\sum_{S\subseteq T}(-1)^{|T|-|S|}f(T)$$

证明的基本思路和前面类似：

首先有：（枚举 $|T|$ 之后就是 $(1-1)^{|S|}$）

$$\sum_{T\subseteq S}(-1)^{|T|}=|S=\varnothing|$$ $$\begin{aligned} g(S)&=\sum_{T\subseteq S}[S-T=\varnothing]g(T) \\ &=\sum_{T\subseteq S}\sum_{A\subseteq S-T}(-1)^{|A|}g(T) \\ &=\sum_{A\subseteq S}(-1)^{|A|}\sum_{T\subseteq S-A}g(T) \\ &=\sum_{A\subseteq S}(-1)^{|S|-|A|}\sum_{T\subseteq A}g(T) \\ &=\sum_{A\subseteq S}(-1)^{|S|-|A|}f(A) \end{aligned}$$

得证。

如果扩展到多重集合，如何构造容斥系数 $\mu$ 使得 $\sum\limits_{T\subseteq S}\mu(T)=[S=\varnothing]$？

只需要让重复的元素都不起作用，对贡献为 $0$ 即可，也就是 $\mu(S)=(-1)^{|S|}[S中无重复元素]$．

于是：

$$f(S)=\sum_{T\subseteq S}g(T)\Longleftrightarrow g(S)=\sum_{T\subseteq S}\mu(S-T)f(T)$$

注意到前文提到的 “莫比乌斯反演” 实际上就是把每个质因子看成一个元素，把每一个数看成一个集合，做这个多重集合的反演，本质上是相同的。

vfk的PPT 中提到了可以拿来算 and,or 卷积，仔细理一下会发现实际上就是 FMT / 高维前缀/后缀和。

FMT

试试从子集反演的角度理解 FMT。

给定长度为 $2^n$ 的数列 $a,b$，计算 $c$ 满足：

$$c_n=\sum_{i|j=n}a_ib_j$$

$n\leq 20$．

也可以称之为 $or$ 卷积？

把下标看成集合：

$$c_n=\sum_{u\cup v=n}a_ub_v$$

直接计算似乎很难，考虑计算出 $c’_n=\sum\limits_{u\subseteq n}c_u$，然后把 $c’$ 还原成 $c$．

$$\begin{aligned} c'_n&=\sum_{u\cup v\subseteq n}a_ub_v \\ &=\sum_{u\subseteq n}\sum_{v\subseteq v}a_ub_v \\ &=\sum_{u\subseteq n}a_u\sum_{v\subseteq n}b_v \\ &=a'_ub'_v \end{aligned}$$

已知 $a,b$ 求 $a’,b’$，可以用高维前缀和完成。

$a$ 到 $a’$ 的映射就是 FMT 啦（

已知 $c’$ 求 $c$，就是高维前缀差分了，这个映射就是 IFMT。但其实也可以利用子集反演证明：

$$c'_n=\sum_{u\subseteq n}c_u\Longleftrightarrow c_n=\sum_{u\subseteq n}(-1)^{|n|-|u|}c'_u$$

计算 $and$ 卷积也同理，把子集换成超集再来一遍就可以了。

FWT

既然都说到了 FMT，自然要提提 FWT？虽然这个东西和子集反演没有什么关系（

回顾 FMT 的过程，实际上我们是构造了一个可逆的变换 $F$ 满足 $F(c)=F(a)\cdot F(b)$，$or$ 卷积是高维前缀和/差分，$and$ 卷积是高维后缀和/差分。

给定长度为 $2^n$ 的数列 $a,b$，计算 $c$ 满足：

$$c_n=\sum_{i\oplus j=n}a_ib_j$$

$n\leq 20$．

感觉还是背柿子比较好，以后有了新的理解大概会回来更新（

$A_0$ 为 $A$ 的偶数下标处组成的序列，$A_1$ 为奇数下标处，$(A,B)$ 指的是将序列 $A$ 和 $B$ 拼接。

$$FWT(A)=(FWT(A_0)+FWT(A_1),FWT(A_0)-FWT(A_1))$$

这个式子和 FFT 的很像。

$$IFWT(A)=(\frac{IFWT(A_0)+IFWT(A_1)}{2},\frac{IFWT(A_0)-IFWT(A_1)}{2})$$

通过 $FWT$ 的式子易推得这个式子。

单位根反演

论文哥：感觉就像是把dft推式子证法中这东西抠了出来起了个名字。没在oi外的地方听说这东西还有类似这样的名字，像是近几年的oi造的名词。

记 $n$ 次单位根为 $\omega_n$．

显然有：

$$\frac{1}{n}\sum_{k=0}^{n-1}\omega_n^{vk}=[v\bmod n = 0]$$

等比数列求和，由于 $v\bmod n=0$ 的时候公比为 $1$ 要特判。

例题

LOJ6485 LJJ 学二项式定理

$$\begin{aligned} ans&=\sum\binom{n}{i}s^i\sum_{j=0}^3\frac{1}{4}\sum_{k=0}^3\omega_{4}^{(i-j)k} \\ &=\frac{1}{4}\sum_{j=0}^3a_j\sum_{k=0}^3\sum\binom{n}{i}s^i\omega_{4}^{(i-j)k} \\ &=\frac{1}{4}\sum_{j=0}^3a_j\sum_{k=0}^3\omega_4^{-jk}\sum\binom{n}{i}s^i\omega_{4}^{ik} \\ &=\frac{1}{4}\sum_{j=0}^3a_j\sum_{k=0}^3\omega_4^{-jk}(s\omega_{4}^{k}+1)^n \end{aligned}$$

min-max 容斥

$$\max(S)=\sum_{\varnothing\neq T\subseteq S}(-1)^{|T|-1}\min(T) \\ \min(S)=\sum_{\varnothing\neq T\subseteq S}(-1)^{|T|-1}\max(T)$$

众做周知 $\max$ 和 $\min$ 是一样的，把优先级反过来即可。

现在证明上面那个式子，大体思路为：设出容斥系数，考虑每个元素是否能贡献列出式子，然后二项式反演得到容斥系数。

设容斥系数为 $f$，也就是 $\max(S)=\sum_{\varnothing\neq T\subseteq S}f(|T|)\min(T)$，钦点一个元素的编号为它的从小到大的排名，则排名为 $k$ 的元素的是否能贡献为：

$$\sum_{i=0}^{n-k}\binom{n-k}{i}f(i+1)=[n-k=0]$$

令 $F(n)=f(n+1),G(n)=[n==0]$，则有：

$$\sum_{i=0}^n\binom{n}{i}F(i)=G(n)$$

二项式反演：

$$\begin{aligned} F(n)&=\sum_{i=0}^n(-1)^{n-i}\binom{n}{i}G(i) \\ f(n+1)&=\sum_{i=0}^n(-1)^{n-i}\binom ni [i==0]=(-1)^n \end{aligned}$$

则 $f(n)=(-1)^{n-1}$．

证毕。

如果左边的 $\max$ 是第 $k$ 大，推导也同理，可得：

$$k\text{-}th\max(S)=\sum_{\varnothing T\subseteq S}(-1)^{|T|-k}\binom{|T|-1}{k-1}\min(T)$$

值得注意的是如果将 $\max/\min$ 换成期望即 $E(\max)/E(\min)$ ，也就是期望意义下的 $\min\text{-}\max$ 容斥也是对的，形式化来讲：

设全集 $U=\{X_1,X_2,…,X_n\}$，其中 $X_i$ 为互相独立的随机变量并且存在 $E(X_i)$，则有：

$$E(\max(S))=\sum_{\varnothing\neq T\subseteq S}(-1)^{|T|-1}E(\min(T))$$

$\max$ 和 $\min$ 互换，以及第 $k$ 大的 $\min\text{-}\max$ 容斥在期望意义下也成立。

证明很简单：

$$\max(S)=\sum_{\varnothing\neq T\subseteq S}(-1)^{|T|-1}\min(T) \\ E(\max(S))=E\left(\sum_{\varnothing\neq T\subseteq S}(-1)^{|T|-1}\min(T)\right)$$

由期望的线性性可得：

$$E(\max(S))=\sum_{\varnothing\neq T\subseteq S}(-1)^{|T|-1}E(\min(T))$$

例题

一个小例子

我们知道，若干个数的 $\gcd$ 相当于单独考虑每个质因子，在各个数里面的指数拿出来组成一个可重集然后取 $\min$，最后再把每个质因子以及对应的次幂乘起来。$\text{lcm}$ 也是同理，于是我们可以对这个指数组成的可重集进行 $\min\text{-}\max$ 容斥来做到 $\gcd$ 和 $\text{lcm}$ 的转换。

更具体地假如说有 $\gcd(S),\text{lcm}(S)$ 分别代表集合 $S$ 中所有数的 $\gcd,\text{lcm}$，则有：

$$\text{lcm}(S)=\prod_{\varnothing\neq T\subseteq S}\gcd(T)^{(-1)^{|T|-1}}$$

$\gcd$ 转成 $\text{lcm}$ 来也是同理。

例题一 HAOI2015 按位或

二进制为 $1$ 的数位看成一个元素，每个数看成一个集合。

定义每个元素的权值为第一次变成 $1$ 的时间，那么可以定义每个集合的 $\max,\min$．

所求即为 $\max(U)$，其中 $U$ 为全集，现在要对任意一个集合 $S$ 计算 $\min(S)$．

考虑枚举时间，计算其对期望的贡献。

定义一个集合 $S$ 包含的元素的出现概率和（或者说与 $S$ 有交的集合的概率和）为 $p_{S}$，$i$ 时刻第一次取到 $S$ 中的元素，前 $(i-1)$ 个时刻一定都没有取到 $S$ 中的元素，则有：

$$\begin{aligned} \min(S)&=\sum_{i=1}^{+\infty}iP(\min(S)=i) \\ &=\sum_{i=1}^{+\infty}i(1-p_S)^{i-1}p_S \\x\gets 1-p_S \\ &=\sum_{i=1}^{+\infty}ix^{i-1}(1-x) \\ &=\sum_{i=1}^{+\infty}ix^{i-1}-ix^i \\ &=x^0+\sum_{i=1}^{+\infty}(i+1)x^{i}-ix^i \\ &=\sum_{i=0}^{+\infty}x^i \\ &=\frac{1}{1-x}=\frac{1}{p_S} \end{aligned}$$

其实就是每一步成功概率为 $p$，则期望成功步数为 $\frac{1}{p}$．

$p_S$ 怎么求？注意到 $x=1-p_S$ 为所有与 $S$ 无交的集合概率和，也就是其补集的子集和，高维前缀和计算即可。

Reference

炫酷反演魔术 vfleaking的博客

斯特林数入门 Hongzy

具体数学 6.1 斯特林数

狄利克雷相关 command_block 的博客

斯特林数学习笔记 Sshwy’s Notes