反演定理及其应用_反演定理的证明

大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全家桶1年46，售后保障稳定

一、莫比乌斯反演

莫比乌斯反演公式：
若

$$F(n)=\sum_{i|n}f(i)$$

则

$$f(n)=\sum_{i|n}\mu(i)F(\frac{n}{i})$$

为什么呢？请看证明：

由于莫比乌斯函数具有性质

∑i|nμ(i)=[n=1] ∑ i | n μ ( i ) = [ n = 1 ]
$\sum_{i|n}\mu(i)=[n=1]$，因此我们考虑把原式带入：

$$\sum_{i|n}\mu(i)\sum_{j|\frac ni}f(i)=\sum_{j|n}f(j)\sum_{i|\frac nj}\mu(i)=\sum_{j|n}f(j)[\frac nj=1]=f(n)$$

证毕。

莫比乌斯反演的另一种形式：

若

$$F(n)=\sum_{n|i}f(i)$$

则

$$f(n)=\sum_{n|i}\mu(\frac in)F(i)$$

证明过程与上面的相仿。

例题：BZOJ1101

给定$n,m，求\sum\limits_{i=1}^n\sum\limits_{j=1}^m[gcd(i,j)=k]$。
设

$$f(k)=\sum_{i=1}^n\sum_{j=1}^m[gcd(i,j)=k]$$

$$F(k)=\sum_{k|i}f(i)=\sum_{i=1}^n\sum_{j=1}^m[k|gcd(i,j)]=\left \lfloor \frac nk\right \rfloor\left \lfloor \frac mk\right \rfloor$$

则根据莫比乌斯反演定理，

$$f(k)=\sum_{k|i}\mu(\frac ik)F(i)=\sum_{k|i}\mu(\frac ik)\left \lfloor \frac ni\right \rfloor\left \lfloor \frac mi\right \rfloor=\sum_{i=1}^{n/k}\mu(i)\left \lfloor \frac n{ki}\right \rfloor\left \lfloor \frac m{ki}\right \rfloor$$

于是变成了一个很显然的整除分块，复杂度

O(Tn−−√) O ( T n )
$O(T\sqrt n)$。

二、二项式反演

若

$$F(n)=\sum_{i=p}^n\binom nif(i)$$

则

$$f(n)=\sum_{i=p}^n(-1)^{n-i}\binom niF(i)$$

证明如下：

$$\sum_{i=p}^n(-1)^{n-i}\binom niF(i)=\sum_{i=p}^n(-1)^{n-i}\binom ni\sum_{j=p}^n\binom ijf(j) \\=\sum_{j=p}^nf(j)\sum_{i=j}^n(-1)^{n-i}\binom ni\binom ij \\=\sum_{j=p}^nf(j)\binom nj\sum_{i=j}^n(-1)^{n-i}\binom{n-j}{i-j} \\=\sum_{j=p}^nf(j)\binom nj\sum_{i=0}^{n-j}(-1)^{n-j-i}\binom{n-j}{i} \\=\sum_{j=p}^nf(j)\binom nj·0^{n-j}$$

最后一步是逆用二项式定理，展开

(1−1)n−j ( 1 − 1 ) n − j
$(1-1)^{n-j}$，发现只有当

n=j n = j
$n=j$时

0n−j=1 0 n − j = 1
$0^{n-j}=1$，因此

$$\sum_{j=p}^nf(j)\binom nj·0^{n-j}=f(n)$$

证毕。

另一种形式：若

$$g(m)=\sum_{i=m}^n\binom imf(i)$$ 则

$$f(m)=\sum_{i=m}^n(-1)^{i-m}\binom img(i)$$

证明过程与上述过程相仿

例题

染色问题

有n个格子排成一排，用$m(m\ge 2)$种颜色染色，求使得相邻格子不能染上相同颜色，且每种颜色都要用上的染色方案数。$(m\le 100,000,n\le 10^9)$
直接计算不好处理，考虑去掉某个限制条件。设$f(m)$为原题答案，$g(m)$为相同格子不能染上相同颜色，至多用m种的染色方案，则显然有$g(m)=m(m-1)^{n-1}$。我们考虑使用$f$计算出
g

$\mathrm{<br>\; g<br>}$

$g$，可以枚举具体使用了哪些颜色，则：

$$g(m)=\sum_{i=2}^m\binom mif(i)$$

根据二项式反演，我们就可以得到：

$$f(m)=\sum_{i=2}^m(-1)^{m-i}\binom mig(i)=\sum_{i=2}^m(-1)^{m-i}\binom mii(i-1)^{n-1}$$

于是题目就可以在

O(mlogn) O ( m l o g n )
$O(mlogn)$的时间内解决。

洛谷8月月赛T4

给定一张$n\times m(m\ge n)$的棋盘，求在这个棋盘上放置$2n$个炮使得他们互不攻击的方案数。
$(n\le m\le 2,000或(m-n\le 10 且 n\le m\le 100,000))$
分析题目，会发现每行必然出现两个炮。由于每列出现的数量也不超过2，考虑把原问题转化为：
给定$1到m共m$种数字，每种数字有两个。现在将它们组合成$n$对无序二元组，每个二元组当中两个数字不同的方案数。
原问题不方便直接计算，我们考虑把“每个二元组当中两个数字不同”的限制去掉。但由于原题求的是无序二元组，在不确定每个二元组中数字是否相同的情况下也非常难计算。于是我们把“无序二元组”变为“有序二元组”。
设
f(n,m)为原题答案，g(n,m)

$\mathrm{<br>\; f<br>}$

(


n


,


m


)



为




原




题




答




案




，



g


(


n


,


m


)

$f(n,m)为原题答案，g(n,m)$为满足上述条件的方案数。考虑如何求$g(n,m)$。
注意到最特殊的情况就是有一些种类的数我们把两个全部选进去了，考虑我们选了多少个这样的数字，又有多少种填入的方案。剩下来的种类中必然是每种选择一个，填入剩下的格子中。于是我们有：

$$g(n,m)=\sum_{i=0}^m\binom mi\frac{A_{2n}^{2i}}{2^i}A_{m-i}^{2n-2i}$$

于是

g(n,m) g ( n , m )
$g(n,m)$便可以在

O(m) O ( m )
$O(m)$的时间内计算出来。但是题目给

m−n≤10 m − n ≤ 10
$m-n\le 10$的条件干什么呢？观察上述算式，会发现若

2i>2n或2n−2i>m−i时A2i2n或A2n−2im−i就为0了 2 i > 2 n 或 2 n − 2 i > m − i 时 A 2 n 2 i 或 A m − i 2 n − 2 i 就 为 0 了
$2i>2n或2n-2i>m-i时A_{2n}^{2i}或A_{m-i}^{2n-2i}就为0了$，无需计算。

解上述不等式可以发现

2n−m≤i≤n 2 n − m ≤ i ≤ n
$2n-m\le i\le n$，因此我们只需要在

max(2n−m,0)≤i≤n m a x ( 2 n − m , 0 ) ≤ i ≤ n
$max(2n-m,0)\le i\le n$的范围中求解即可。

$$g(n,m)=\sum_{i=max(2n-m,0)}^n\binom mi\frac{A_{2n}^{2i}}{2^i}A_{m-i}^{2n-2i}$$

这个范围大小就是

O(m−n) O ( m − n )
$O(m-n)$级别的了。

我们再考虑如何通过

g(n,m)求出f(n,m) g ( n , m ) 求 出 f ( n , m )
$g(n,m)求出f(n,m)$。

f和g f 和 g
$f和g$之间一个非常大的区别就是要求二元组中的数字是否相同。我们考虑枚举有多少个二元组中数字相同，别忘了还要把无序变为有序。于是可以得到：

$$g(n,m)=\sum_{i=0}^n\binom niA_m^i2^{n-i}f(n-i,m-i)$$

于是可以想到二项式反演。但是上面那个算式不方便于反演，我们可以稍微转化一下。

$$\frac{g(n,m)}{m!}=\sum_{i=0}^n\binom ni\frac{2^{n-i}f(n-i,m-i)}{i!}$$

考虑到无论是

f,g f , g
$f,g$，他们在题目中能够使用到的两个下标差值均为

n−m n − m
$n-m$。于是令：

$$F(i)=\frac{2^if(i,i-n+m)}{(i-n+m)!}，G(i)=\frac{g(i,i-n+m)}{(i-n+m)!}$$

在加上组合数的左右值对称，于是上面的算式就变成二项式反演的模型了。

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

$$F(n)=\sum_{i=0}^n(-1)^{n-i}\binom niG(i)$$

再根据

F,G F , G
$F,G$的定义，把

f,g f , g
$f,g$带入得到：

$$f(n,m)=\frac{m!}{2^n}\sum_{i=0}^n(-1)^i\binom ni\frac{g(n-i,m-i)}{(m-i)!}$$

至此，这道题目就可以在

O(min(n,m−n)×n) O ( m i n ( n , m − n ) × n )
$O(min(n,m-n)\times n)$的时间内解决了。

三、斯特林反演

第一类斯特林数

第一类斯特林数分为有符号和无符号两种，这里仅讨论无符号的情况。
下面记$s(n,k)$为无符号第一类斯特林数。
定义：

$$x^{\underline{n}}=\prod_{i=x-n+1}^xi=\sum_{i=0}^n(-1)^{n-i}s(n,i)x^i$$

也就是说，
有符号第一类斯特林数是

x x
$x$的


n

$\mathrm{<br>\; n<br>}$

$n$阶下降幂展开式的系数。

定义：

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

也就是说，
无符号第一类斯特林数是

x x
$x$的


n

$\mathrm{<br>\; n<br>}$

$n$阶上升幂展开式的系数。根据定义，我们可以使用分治NTT在

O(nlog2n) O ( n l o g 2 n )
$O(nlog^2n)$的时间内预处理出第一类斯特林数。

组合数学性质：

s(n,k) s ( n , k )
$s(n,k)$表示将

n个数划分为k n 个 数 划 分 为 k
$n个数划分为k$个无区别非空环的方案数。

递推式：

$$s(n,k)=s(n-1,k-1)+(n-1)s(n-1,k)$$

性质：

$$\sum_{i=0}^ns(n,i)=n!$$

证明：我们假设一个

1到n排列为p 1 到 n 排 列 为 p
$1到n排列为p$，定义一次置换为将

i位置上的数pi与pi i 位 置 上 的 数 p i 与 p i
$i位置上的数p_i与p_i$位置上的数字交换。则排列可以被划分为若干个环。如2,4,3,1,5，根据置换我们可以把排列分为(2,4,1),(3),(5)三个环。显然的，环的划分与每个排列一一对应，根据第一类斯特林数的组合数学性质，可以证明。

第二类斯特林数

定义：$S(n,k)$表示将n个数字分为k个无区别非空集合的方案数。
递推式：

$$S(n,k)=S(n-1,k-1)+kS(n-1,k)$$

根据定义，可以得到如下性质：

$$k^n=\sum_{i=1}^k\binom kiS(n,i)i!$$

这个公式也比较好理解，我们排除掉非空的条件，并且把无区别变为有区别，枚举共有多少个非空集合即可。

于是根据二项式反演，我们可以得到

$$S(n,k)=\frac{1}{k!}\sum_{i=1}^k(-1)^{k-i}\binom kii^n=\sum_{i=0}^k\frac{(-1)^{k-i}}{(k-i)!}·\frac{i^n}{i!}$$

因为

i i
$i$从0开始和从1开始没有什么区别。观察到最后的形式其实是一个卷积，因此我们可以通过NTT在


O(nlogn)

$\mathrm{<br>\; O<br>}$

(


n


l


o


g


n


)

$O(nlogn)$的时间内预处理数第二类斯特林数。

第二类斯特林数的性质还有一个表述，就是

$$k^n=\sum_{i=1}^n\binom kiS(n,i)i!$$ 也就是将

i的上界由k变为n i 的 上 界 由 k 变 为 n
$i的上界由k变为n$。其实也非常好理解，因为若

i>k，则(ki)=0；若n<k，则对于i>n也有S(n,i)=0 i > k ， 则 ( k i ) = 0 ； 若 n < k ， 则 对 于 i > n 也 有 S ( n , i ) = 0
$i>k，则\binom ki=0；若n<k，则对于i>n也有S(n,i)=0$，不会影响计算结果。

利用第二类斯特林数的性质，我们可以处理出自然数幂和。

先证明一个引理：

$$\sum_{i=m}^n\binom im=\binom{n+1}{n-m}（边界条件定义：若b<0或b>a则\binom ab=0）$$

显然，当

n=0 n = 0
$n=0$时无论

m m
$m$取何非负整数都满足要求，或当


m=0时n

$\mathrm{<br>\; m<br>}$

=


0



时



n

$m=0时n$取任何非负整数也满足要求。接下来证明若

n,m和n,m+1满足，则n+1,m+1也满足 n , m 和 n , m + 1 满 足 ， 则 n + 1 , m + 1 也 满 足
$n,m和n,m+1满足，则n+1,m+1也满足$。

$$\sum_{i=m+1}^{n+1}\binom{i}{m+1}=\sum_{i=m}^n\binom{i}{m+1}+\binom im=\binom{n+1}{n-m}+\binom{n+1}{n-m-1}=\binom{n+2}{(n+1)-(m+1)}$$

引理得证，接下来开始计算自然数幂和。

$$\sum_{i=1}^ni^k=\sum_{i=1}^n\sum_{j=1}^{min(i,k)}\binom ijS(k,j)j!=\sum_{j=1}^kS(k,j)j!\sum_{i=j}^n\binom ij\\=\sum_{j=1}^kS(k,j)j!\binom{n+1}{n-j}=\sum_{j=1}^kS(k,j)\frac{(n+1)^{\underline{j+1}}}{j+1}$$

由于

(n+1)j+1–––– ( n + 1 ) j + 1 _
$(n+1)^{\underline{j+1}}$是由

j+1 j + 1
$j+1$个连续整数相乘，必然有一个为

j+1 j + 1
$j+1$的倍数。因此这种方法可以在

O(k2) O ( k 2 )
$O(k^2)$的时间内处理出任何模数下的自然数幂和。如果模数类似于998244353，我们可以先用NTT预处理出所有的第二类斯特林数，再预处理出

n+1 n + 1
$n+1$的下降幂和正整数逆元，可以在

O(klogk) O ( k l o g k )
$O(klogk)$的时间计算出自然数幂和。

性质应用例题BZOJ2159

给定一棵树，每条边边权为1，对于每个节点$u，求\sum\limits_{i=1}^ndist(u,i)^k$。
考虑应用第二类斯特林数的性质

$$\sum_{i=1}^ndist(u,i)^k=\sum_{i=1}^n\sum_{j=1}^kS(k,j)\binom{dist(u,i)}jj!=\sum_{j=1}^kS(k,j)j!\sum_{i=1}^n\binom{dist(u,i)}j$$

则对于每个节点，都计算出

∑i=1n(dist(u,i)j) ∑ i = 1 n ( d i s t ( u , i ) j )
$\sum\limits_{i=1}^n\binom{dist(u,i)}j$即可。我们分两次进行树形dp，第一次统计每个节点和它子树当中所有点的和，记为

f(u,j)，则f(u,j)=∑v∈son[u]f(v,j−1)+f(v,j) f ( u , j ) ， 则 f ( u , j ) = ∑ v ∈ s o n [ u ] f ( v , j − 1 ) + f ( v , j )
$f(u,j)，则f(u,j)=\sum\limits_{v\in son[u]}f(v,j-1)+f(v,j)$，第二次统计每个节点除子树外的所有节点的和，记为

g(u,j)，则g(u,j)=g(fa[u],j)+g(fa[u],j−1)+∑v∈son[fa[u]]且v≠uf(v,j−2)+2f(v,j−1)+f(v,j) g ( u , j ) ， 则 g ( u , j ) = g ( f a [ u ] , j ) + g ( f a [ u ] , j − 1 ) + ∑ v ∈ s o n [ f a [ u ] ] 且 v ≠ u f ( v , j − 2 ) + 2 f ( v , j − 1 ) + f ( v , j )
$g(u,j)，则g(u,j)=g(fa[u],j)+g(fa[u],j-1)+\sum\limits_{v\in son[fa[u]]且v\ne u}f(v,j-2)+2f(v,j-1)+f(v,j)$，后面那个求和预处理一下

s(j)=∑v∈son[fa[u]]f(v,j) s ( j ) = ∑ v ∈ s o n [ f a [ u ] ] f ( v , j )
$s(j)=\sum\limits_{v\in son[fa[u]]}f(v,j)$，计算的时候减去自己即可。总复杂度

O(nk+k2) O ( n k + k 2 )
$O(nk+k^2)$。

反演公式

若

$$g(n)=\sum_{i=m}^nS(n,i)f(i)$$

则

$$f(n)=\sum_{i=m}^n(-1)^{n-i}s(n,i)g(i)$$

其中大写

S S
$S$表示第二类斯特林数，小写


s

$\mathrm{<br>\; s<br>}$

$s$表示第一类斯特林数。

证明：

$$\sum_{i=m}^n(-1)^{n-i}s(n,i)g(i)$$

$$=\sum_{i=m}^n(-1)^{n-i}s(n,i)\sum_{j=m}^iS(i,j)f(j)$$

$$=\sum_{j=m}^nf(j)\sum_{i=j}^n(-1)^{n-i}s(n,i)S(i,j)$$

考虑两类斯特林数的性质，有

$$x^{\underline n}=\sum_{i=1}^n(-1)^{n-i}s(n,i)x^i=\sum_{i=1}^n(-1)^{n-i}s(n,i)\sum_{j=1}^iS(i,j)x^{\underline j}$$

$$=\sum_{j=1}^nx^{\underline j}\sum_{i=j}^n(-1)^{n-i}s(n,i)S(i,j)$$

根据上述等式，我们发现只有当

j=n j = n
$j=n$时后面算式的值才应当为1，其他时刻全为0.因此：

$$\sum_{i=m}^n(-1)^{n-i}s(n,i)g(i)=f(n)$$

证毕。

我们其实会发现斯特林反演和二项式反演的形式很像，那二项式反演的第二种形式斯特林反演是否满足呢？满足。

$$g(m)=\sum_{i=m}^nS(i,m)f(i)，则f(m)=\sum_{i=m}^n(-1)^{i-m}s(i,m)g(i)$$

用类似二项式反演的办法可以得到

$$\sum_{i=m}^n(-1)^{i-m}s(i,m)g(i)=\sum_{j=m}^nf(j)\sum_{i=m}^j(-1)^{i-m}S(j,i)s(i,m)$$

再次考虑他们的性质，换一种方法可以得到：

$$x^n=\sum_{i=1}^nS(n,i)x^{\underline i}=\sum_{i=1}^nS(n,i)\sum_{j=1}^i(-1)^{i-j}s(i,j)x^j$$

$$=\sum_{j=1}^nx^j\sum_{i=j}^n(-1)^{i-j}S(n,i)s(i,j)$$

仍然会有后面的部分为1当且仅当

j=n j = n
$j=n$。于是把这个性质带入回去，也就是把上式的

j j
$j$变为


m

$\mathrm{<br>\; m<br>}$

$m$，

n n
$n$变为


j

$\mathrm{<br>\; j<br>}$

$j$，就会发现只有当

j=m j = m
$j=m$的时候上式的值才为1.因此

$$\sum_{j=m}^nf(j)\sum_{i=m}^j(-1)^{i-m}S(j,i)s(i,m)=f(m)$$

证毕。

例题BZOJ4617

定义两个结点数相同的图G1与图G2的异或为一个新的图G, 其中如果(u,v)在G1与G2中的出现次数之和为1, 那么边(u,v)在G中, 否则这条边不在G中.现在给定s个结点数相同的图G1…s, 设S=G1,G2,…,Gs, 请问S有多少个子集的异或为一个连通图?

直接做是不好做的，我们考虑差分（容斥）。发现节点数很小，于是可以想到去在节点数上面做手脚。定义$f(i)为异或图中连通块个数恰好为i的方案数，g(i)为异或图中连通块个数大于等于i的方案数。考虑怎么求g(i)$。

我们可以考虑枚举最终的连通块有哪些，此时花费的时间为n的贝尔数，最大为115975。此时我们限定枚举出的子集之间不能连边，子集内部随便连不连。枚举每一个子图，看看这个子图含有哪些子集之间的边，每个子图标记一个01串。我们最终要求这些01串异或起来的结果中有多少个为全0串。

可以把这些01串全部插入到线性基中，找出自由元的数量为$x，则方案数为2^x$。为什么呢？对于任何一个自由元的子集，它们异或出来的结果必然也可以用主元代替，这就对应了一个全0串的情况。

于是我们用$O(bell(n)n^2s)$的时间算出了所有的$g$，接下来算出
f

$\mathrm{<br>\; f<br>}$

$f$即可。

根据定义，有

$$g(m)=\sum_{i=m}^nS(i,m)f(i)$$ 因为计算的时候我们相当于把

i i
$i$个连通块划分成了


m

$\mathrm{<br>\; m<br>}$

$m$个子集。

于是根据斯特林反演，我们可以得到

$$f(m)=\sum_{i=m}^n(-1)^{i-m}s(i,m)g(i)$$

于是我们最终可以求出

f(1) f ( 1 )
$f(1)$，整个问题便解决了。