莫比乌斯反演 引入定理 另一种莫比乌斯反演 证明性质求莫比乌斯函数值例题及题解 二项式反演 反演公式例题 bzoj3622涂色问题 DescriptionSolution Stirling反演 第一类斯特林数 递推方式 第二类斯特林数 求法 递推容斥 性质例题 CF 932E DescriptionSolution BZOJ2159 反演公式 例题

莫比乌斯反演

引入

莫比乌斯反演一般都是先定义一个函数 F(n) F ( n ) ,再由 F(n) F ( n ) 定义函数 G(n) G ( n ) ： G(n)=ΣF(d) G ( n ) = Σ F ( d ) ,其中 d d 被包含于nn。我们只知道 G(n) G ( n ) 的值，由 G(n) G ( n ) 反推 F(n) F ( n ) ，这个过程就叫做“反演”。 例： S S 、XX是两个集合，先定义 F(S) F ( S ) ，再定义 G(S)=ΣF(X) G ( S ) = Σ F ( X ) ，其中 X X 为SS的一个子集。如果已知 G G 的值，便可以通过关于集合包含的公式：F(S)=Σ((−1)|S|−|X|∗G(X))F(S)=Σ((−1)|S|−|X|∗G(X)) 而反演的实质就是容斥！

定理

定义F(n)和f(n)是定义在非负整数集合上的两个函数，且满足 F(n)=∑d|nf(d) F ( n ) = ∑ d | n f ( d ) ，那么 f(n)=∑d|nμ(d)F(nd) f ( n ) = ∑ d | n μ ( d ) F ( n d ) 。 其中 μ(d) μ ( d ) 的定义如下：

若 d=1 d = 1 ，那么 μ(d)=1 μ ( d ) = 1 若 d=p1×p2⋯×pk d = p 1 × p 2 ⋯ × p k ， pi p i 为互异素数，那么 μ(d)=(−1)k μ ( d ) = ( − 1 ) k 其他情况下 μ(d)=0 μ ( d ) = 0

另一种莫比乌斯反演

F(n)=∑n|df(d)⇒f(n)=∑n|dμ(dn)F(d) F ( n ) = ∑ n | d f ( d ) ⇒ f ( n ) = ∑ n | d μ ( d n ) F ( d )

---

证明

∑d|nμ(d)F(nd)=∑d|nμ(d)∑d′ndf(d′)=∑d′|nf(d′)∑d|nd′μ(d)=f(n) ∑ d | n μ ( d ) F ( n d ) = ∑ d | n μ ( d ) ∑ d ′ n d f ( d ′ ) = ∑ d ′ | n f ( d ′ ) ∑ d | n d ′ μ ( d ) = f ( n ) Q.E.D.!

性质

1.

∑d|nμ(d)={10,n=1,n>1 ∑ d | n μ ( d ) = { 1 , n = 1 0 , n > 1 2. ∑d|nμ(d)d=φ(n)n ∑ d | n μ ( d ) d = φ ( n ) n

求莫比乌斯函数值

套线性筛的板子

void Get_mu(int n) { Set(flag , 0); flag[0] = flag[1] = 1; cnt = 0; mu[1] = 1; For(i , 2 , n) { if (!flag[i]) { prime[++ cnt] = i; mu[i] = -1; } for (int j = 1 ; j <= cnt && i * prime[j] <= n ; ++ j) { flag[i * prime[j]] = 1; if (!(i % prime[j])) { mu[i * prime[j]] = 0; break; } mu[i * prime[j]] = - mu[i]; } } For(i , 1 , n) printf("%d\n" , mu[i]); }

例题及题解

BZOJ1101 BZOJ3994 BZOJ3930 BZOJ3201 BZOJ2005 HDU1695

---

二项式反演

反演公式

f(n)=∑k=pn(nk)g(k) f ( n ) = ∑ k = p n ( n k ) g ( k ) ⇕ ⇕ g(n)=∑k=pn(−1)n−k(nk)f(k) g ( n ) = ∑ k = p n ( − 1 ) n − k ( n k ) f ( k )

例题

bzoj3622

题解

涂色问题

Description

有个 1×n 1 × n 的格子， m m 种颜色（m≥2m≥2），要求相邻格子的颜色不相同且每种颜色都要用到，求染色方案数。

Solution

设 f(n) f ( n ) 为恰好用了 n n 种颜色的方案数，g(n)g(n)为至多用了 n n 种颜色的方案数。 那么有：g(k)=k(k−1)n−1=∑i=2k(ki)f(i)g(k)=k(k−1)n−1=∑i=2k(ki)f(i) 由二项式反演得：

f(k)=∑i=2k(−1)k−i(ki)g(i) f ( k ) = ∑ i = 2 k ( − 1 ) k − i ( k i ) g ( i )

---

Stirling反演

第一类斯特林数

[nm] [ n m ] 表示将 n n 个元素排成kk个轮换的方法数。

递推方式

[nm]=[n−1m−1]+(n−1)[n−1m] [ n m ] = [ n − 1 m − 1 ] + ( n − 1 ) [ n − 1 m ]

第二类斯特林数

gzy’s blog {nm} { n m } 表示将 n n 个元素划分成kk个非空子集的方法数。

求法

递推

{nm}={n−1m−1}+m{n−1m} { n m } = { n − 1 m − 1 } + m { n − 1 m }

容斥

{nm}=1m!∑k=0m(−1)k(mk)(m−k)n { n m } = 1 m ! ∑ k = 0 m ( − 1 ) k ( m k ) ( m − k ) n 理解：枚举盒子的个数，其他的随便乱放，由于盒子视作相同，所以除以 m! m ! 。

整理该式得：

{nm}=∑k=0m(−1)k×1k!×(m−k)n(m−k)! { n m } = ∑ k = 0 m ( − 1 ) k × 1 k ! × ( m − k ) n ( m − k ) ! 发现是卷积的形式，可以用NTT在 O(nlog2n) O ( n log 2 ⁡ n ) 的时间内求解。

性质

nk=∑i=0k{ki}(ni)i! n k = ∑ i = 0 k { k i } ( n i ) i ! 理解：左边是将 k k 个球放在nn个盒子里；右边枚举非空盒子的个数，从 n n 个盒子中选出ii个盒子，将 k k 个球放在这ii个盒子里，由于盒子是不同的，所以乘上 i! i ! 。 这个式子还可以转化为： nk=∑i=1k{ki}ni⎯ n k = ∑ i = 1 k { k i } n i _

例题

CF 932E

参考肖dalao博客

Description

∑i=1n(ni)×ik ∑ i = 1 n ( n i ) × i k

Solution

用上面的性质推式子：

∑i=1n(ni)×ik ∑ i = 1 n ( n i ) × i k =∑i=1n(ni)∑j=1k(ij){kj}×i! = ∑ i = 1 n ( n i ) ∑ j = 1 k ( i j ) { k j } × i ! =∑i=1n∑j=1k{kj}(ni)(ij)×j! = ∑ i = 1 n ∑ j = 1 k { k j } ( n i ) ( i j ) × j ! =n!∑i=1n∑j=1k{kj}1(n−i)!1(i−j)! = n ! ∑ i = 1 n ∑ j = 1 k { k j } 1 ( n − i ) ! 1 ( i − j ) ! =n!∑i=1n∑j=1k{kj}(n−jn−i)1(n−j)! = n ! ∑ i = 1 n ∑ j = 1 k { k j } ( n − j n − i ) 1 ( n − j ) ! =n!∑j=1k{kj}∑i=1n(n−jn−i)1(n−j)! = n ! ∑ j = 1 k { k j } ∑ i = 1 n ( n − j n − i ) 1 ( n − j ) ! =n!∑j=1k{kj}2n−j1(n−j)! = n ! ∑ j = 1 k { k j } 2 n − j 1 ( n − j ) ! =∑j=1k{kj}2n−jnj⎯ = ∑ j = 1 k { k j } 2 n − j n j _

BZOJ2159

题解

反演公式

感觉和二项式反演比较像。

f(n)=∑i=1n{ni}g(i) f ( n ) = ∑ i = 1 n { n i } g ( i ) ⇕ ⇕ g(n)=∑i=1n(−1)n−i[ni]f(i) g ( n ) = ∑ i = 1 n ( − 1 ) n − i [ n i ] f ( i )

例题

异或图 （其实这个题也只是在推容斥系数时候用了一下233）