为您推荐:
精华内容
最热下载
问答
  • 5星
    1KB weixin_42696271 2021-09-11 08:47:59
  • 5星
    15.41MB weixin_42696333 2021-09-10 20:51:04
  • 5星
    145.04MB qq_31988139 2021-08-10 09:54:59
  • 一、莫比乌斯反演 莫比乌斯反演公式: 若 F(n)=∑i|nf(i)F(n)=∑i|nf(i)F(n)=\sum_{i|n}f(i) 则 f(n)=∑i|nμ(i)F(ni)f(n)=∑i|nμ(i)F(ni)f(n)=\sum_{i|n}\mu(i)F(\frac{n}{i}) 为什么呢?请看证明: 由于...

    一、莫比乌斯反演

    莫比乌斯反演公式:

    F(n)=i|nf(i) F ( n ) = ∑ i | n f ( i )


    f(n)=i|nμ(i)F(ni) f ( n ) = ∑ i | n μ ( i ) F ( n i )

    为什么呢?请看证明:
    由于莫比乌斯函数具有性质 i|nμ(i)=[n=1] ∑ i | n μ ( i ) = [ n = 1 ] ,因此我们考虑把原式带入:
    i|nμ(i)j|nif(i)=j|nf(j)i|njμ(i)=j|nf(j)[nj=1]=f(n) ∑ i | n μ ( i ) ∑ j | n i f ( i ) = ∑ j | n f ( j ) ∑ i | n j μ ( i ) = ∑ j | n f ( j ) [ n j = 1 ] = f ( n )

    证毕。
    莫比乌斯反演的另一种形式:

    F(n)=n|if(i) F ( n ) = ∑ n | i f ( i )


    f(n)=n|iμ(in)F(i) f ( n ) = ∑ n | i μ ( i n ) F ( i )

    证明过程与上面的相仿。

    例题:BZOJ1101

    给定 n,mi=1nj=1m[gcd(i,j)=k] n , m , 求 ∑ i = 1 n ∑ j = 1 m [ g c d ( i , j ) = k ]

    f(k)=i=1nj=1m[gcd(i,j)=k] f ( k ) = ∑ i = 1 n ∑ j = 1 m [ g c d ( i , j ) = k ]
    F(k)=k|if(i)=i=1nj=1m[k|gcd(i,j)]=nkmk F ( k ) = ∑ k | i f ( i ) = ∑ i = 1 n ∑ j = 1 m [ k | g c d ( i , j ) ] = ⌊ n k ⌋ ⌊ m k ⌋

    则根据莫比乌斯反演定理,
    f(k)=k|iμ(ik)F(i)=k|iμ(ik)nimi=i=1n/kμ(i)nkimki f ( k ) = ∑ k | i μ ( i k ) F ( i ) = ∑ k | i μ ( i k ) ⌊ n i ⌋ ⌊ m i ⌋ = ∑ i = 1 n / k μ ( i ) ⌊ n k i ⌋ ⌊ m k i ⌋

    于是变成了一个很显然的整除分块,复杂度 O(Tn) O ( T n )

    二、二项式反演

    F(n)=i=pn(ni)f(i) F ( n ) = ∑ i = p n ( n i ) f ( i )

    f(n)=i=pn(1)ni(ni)F(i) f ( n ) = ∑ i = p n ( − 1 ) n − i ( n i ) F ( i )

    证明如下:
    i=pn(1)ni(ni)F(i)=i=pn(1)ni(ni)j=pn(ij)f(j)=j=pnf(j)i=jn(1)ni(ni)(ij)=j=pnf(j)(nj)i=jn(1)ni(njij)=j=pnf(j)(nj)i=0nj(1)nji(nji)=j=pnf(j)(nj)0nj ∑ i = p n ( − 1 ) n − i ( n i ) F ( i ) = ∑ i = p n ( − 1 ) n − i ( n i ) ∑ j = p n ( i j ) f ( j ) = ∑ j = p n f ( j ) ∑ i = j n ( − 1 ) n − i ( n i ) ( i j ) = ∑ j = p n f ( j ) ( n j ) ∑ i = j n ( − 1 ) n − i ( n − j i − j ) = ∑ j = p n f ( j ) ( n j ) ∑ i = 0 n − j ( − 1 ) n − j − i ( n − j i ) = ∑ j = p n f ( j ) ( n j ) · 0 n − j

    最后一步是逆用二项式定理,展开 (11)nj ( 1 − 1 ) n − j ,发现只有当 n=j n = j 0nj=1 0 n − j = 1 ,因此
    j=pnf(j)(nj)0nj=f(n) ∑ j = p n f ( j ) ( n j ) · 0 n − j = f ( n )

    证毕。
    另一种形式:若
    g(m)=i=mn(im)f(i) g ( m ) = ∑ i = m n ( i m ) f ( i )
    f(m)=i=mn(1)im(im)g(i) f ( m ) = ∑ i = m n ( − 1 ) i − m ( i m ) g ( i )

    证明过程与上述过程相仿

    例题

    染色问题

    有n个格子排成一排,用 m(m2) m ( m ≥ 2 ) 种颜色染色,求使得相邻格子不能染上相同颜色,且每种颜色都要用上的染色方案数。 (m100,000,n109) ( m ≤ 100 , 000 , n ≤ 10 9 )
    直接计算不好处理,考虑去掉某个限制条件。设 f(m) f ( m ) 为原题答案, g(m) g ( m ) 为相同格子不能染上相同颜色,至多用m种的染色方案,则显然有 g(m)=m(m1)n1 g ( m ) = m ( m − 1 ) n − 1 。我们考虑使用 f f 计算出g,可以枚举具体使用了哪些颜色,则:

    g(m)=i=2m(mi)f(i) g ( m ) = ∑ i = 2 m ( m i ) f ( i )

    根据二项式反演,我们就可以得到:
    f(m)=i=2m(1)mi(mi)g(i)=i=2m(1)mi(mi)i(i1)n1 f ( m ) = ∑ i = 2 m ( − 1 ) m − i ( m i ) g ( i ) = ∑ i = 2 m ( − 1 ) m − i ( m i ) i ( i − 1 ) n − 1

    于是题目就可以在 O(mlogn) O ( m l o g n ) 的时间内解决。

    洛谷8月月赛T4

    给定一张 n×m(mn) n × m ( m ≥ n ) 的棋盘,求在这个棋盘上放置 2n 2 n 个炮使得他们互不攻击的方案数。
    (nm2,000(mn10nm100,000)) ( n ≤ m ≤ 2 , 000 或 ( m − n ≤ 10 且 n ≤ m ≤ 100 , 000 ) )
    分析题目,会发现每行必然出现两个炮。由于每列出现的数量也不超过2,考虑把原问题转化为:
    给定 1mm 1 到 m 共 m 种数字,每种数字有两个。现在将它们组合成 n n 对无序二元组,每个二元组当中两个数字不同的方案数。
    原问题不方便直接计算,我们考虑把“每个二元组当中两个数字不同”的限制去掉。但由于原题求的是无序二元组,在不确定每个二元组中数字是否相同的情况下也非常难计算。于是我们把“无序二元组”变为“有序二元组”。
    f(n,m)g(n,m)为满足上述条件的方案数。考虑如何求 g(n,m) g ( n , m )
    注意到最特殊的情况就是有一些种类的数我们把两个全部选进去了,考虑我们选了多少个这样的数字,又有多少种填入的方案。剩下来的种类中必然是每种选择一个,填入剩下的格子中。于是我们有:

    g(n,m)=i=0m(mi)A2i2n2iA2n2imi g ( n , m ) = ∑ i = 0 m ( m i ) A 2 n 2 i 2 i A m − i 2 n − 2 i

    于是 g(n,m) g ( n , m ) 便可以在 O(m) O ( m ) 的时间内计算出来。但是题目给 mn10 m − n ≤ 10 的条件干什么呢?观察上述算式,会发现若 2i>2n2n2i>miA2i2nA2n2imi0 2 i > 2 n 或 2 n − 2 i > m − i 时 A 2 n 2 i 或 A m − i 2 n − 2 i 就 为 0 了 ,无需计算。
    解上述不等式可以发现 2nmin 2 n − m ≤ i ≤ n ,因此我们只需要在 max(2nm,0)in m a x ( 2 n − m , 0 ) ≤ i ≤ n 的范围中求解即可。
    g(n,m)=i=max(2nm,0)n(mi)A2i2n2iA2n2imi g ( n , m ) = ∑ i = m a x ( 2 n − m , 0 ) n ( m i ) A 2 n 2 i 2 i A m − i 2 n − 2 i

    这个范围大小就是 O(mn) O ( m − n ) 级别的了。
    我们再考虑如何通过 g(n,m)f(n,m) g ( n , m ) 求 出 f ( n , m ) fg f 和 g 之间一个非常大的区别就是要求二元组中的数字是否相同。我们考虑枚举有多少个二元组中数字相同,别忘了还要把无序变为有序。于是可以得到:
    g(n,m)=i=0n(ni)Aim2nif(ni,mi) g ( n , m ) = ∑ i = 0 n ( n i ) A m i 2 n − i f ( n − i , m − i )

    于是可以想到二项式反演。但是上面那个算式不方便于反演,我们可以稍微转化一下。
    g(n,m)m!=i=0n(ni)2nif(ni,mi)i! g ( n , m ) m ! = ∑ i = 0 n ( n i ) 2 n − i f ( n − i , m − i ) i !

    考虑到无论是 f,g f , g ,他们在题目中能够使用到的两个下标差值均为 nm n − m 。于是令:
    F(i)=2if(i,in+m)(in+m)!G(i)=g(i,in+m)(in+m)! F ( i ) = 2 i f ( i , i − n + m ) ( i − n + m ) ! , G ( i ) = g ( i , i − n + m ) ( i − n + m ) !

    在加上组合数的左右值对称,于是上面的算式就变成二项式反演的模型了。
    G(n)=i=0n(ni)F(ni)=i=0n(ni)F(i) G ( n ) = ∑ i = 0 n ( n i ) F ( n − i ) = ∑ i = 0 n ( n i ) F ( i )

    F(n)=i=0n(1)ni(ni)G(i) F ( n ) = ∑ i = 0 n ( − 1 ) n − i ( n i ) G ( i )

    再根据 F,G F , G 的定义,把 f,g f , g 带入得到:
    f(n,m)=m!2ni=0n(1)i(ni)g(ni,mi)(mi)! f ( n , m ) = m ! 2 n ∑ i = 0 n ( − 1 ) i ( n i ) g ( n − i , m − i ) ( m − i ) !

    至此,这道题目就可以在 O(min(n,mn)×n) O ( m i n ( n , m − n ) × n ) 的时间内解决了。

    三、斯特林反演

    第一类斯特林数

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

    xn=i=xn+1xi=i=0n(1)nis(n,i)xi x n _ = ∏ i = x − n + 1 x i = ∑ i = 0 n ( − 1 ) n − i s ( n , i ) x i

    也就是说, 有符号第一类斯特林数是 x x n阶下降幂展开式的系数。
    定义:
    xn¯¯¯=i=xx+n1i=i=0ns(n,i)xi x n ¯ = ∏ i = x x + n − 1 i = ∑ i = 0 n s ( n , i ) x i

    也就是说, 无符号第一类斯特林数是 x x n阶上升幂展开式的系数。根据定义,我们可以使用分治NTT在 O(nlog2n) O ( n l o g 2 n ) 的时间内预处理出第一类斯特林数。
    组合数学性质: s(n,k) s ( n , k ) 表示将 nk n 个 数 划 分 为 k 个无区别非空环的方案数。
    递推式:
    s(n,k)=s(n1,k1)+(n1)s(n1,k) s ( n , k ) = s ( n − 1 , k − 1 ) + ( n − 1 ) s ( n − 1 , k )

    性质:
    i=0ns(n,i)=n! ∑ i = 0 n s ( n , i ) = n !

    证明:我们假设一个 1np 1 到 n 排 列 为 p ,定义一次置换为将 ipipi i 位 置 上 的 数 p i 与 p i 位置上的数字交换。则排列可以被划分为若干个环。如2,4,3,1,5,根据置换我们可以把排列分为(2,4,1),(3),(5)三个环。显然的,环的划分与每个排列一一对应,根据第一类斯特林数的组合数学性质,可以证明。

    第二类斯特林数

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

    S(n,k)=S(n1,k1)+kS(n1,k) S ( n , k ) = S ( n − 1 , k − 1 ) + k S ( n − 1 , k )

    根据定义,可以得到如下性质:
    kn=i=1k(ki)S(n,i)i! k n = ∑ i = 1 k ( k i ) S ( n , i ) i !

    这个公式也比较好理解,我们排除掉非空的条件,并且把无区别变为有区别,枚举共有多少个非空集合即可。
    于是根据二项式反演,我们可以得到
    S(n,k)=1k!i=1k(1)ki(ki)in=i=0k(1)ki(ki)!ini! S ( n , k ) = 1 k ! ∑ i = 1 k ( − 1 ) k − i ( k i ) i n = ∑ i = 0 k ( − 1 ) k − i ( k − i ) ! · i n i !

    因为 i i 从0开始和从1开始没有什么区别。观察到最后的形式其实是一个卷积,因此我们可以通过NTT在O(nlogn)的时间内预处理数第二类斯特林数。
    第二类斯特林数的性质还有一个表述,就是
    kn=i=1n(ki)S(n,i)i! k n = ∑ i = 1 n ( k i ) S ( n , i ) i !
    也就是将 ikn i 的 上 界 由 k 变 为 n 。其实也非常好理解,因为若 i>k(ki)=0n<ki>nS(n,i)=0 i > k , 则 ( k i ) = 0 ; 若 n < k , 则 对 于 i > n 也 有 S ( n , i ) = 0 ,不会影响计算结果。
    利用第二类斯特林数的性质,我们可以处理出自然数幂和。
    先证明一个引理:
    i=mn(im)=(n+1nm)b<0b>a(ab)=0 ∑ i = m n ( i m ) = ( n + 1 n − m ) ( 边 界 条 件 定 义 : 若 b < 0 或 b > a 则 ( a b ) = 0 )

    显然,当 n=0 n = 0 时无论 m m 取何非负整数都满足要求,或当m=0n取任何非负整数也满足要求。接下来证明若 n,mn,m+1n+1,m+1 n , m 和 n , m + 1 满 足 , 则 n + 1 , m + 1 也 满 足
    i=m+1n+1(im+1)=i=mn(im+1)+(im)=(n+1nm)+(n+1nm1)=(n+2(n+1)(m+1)) ∑ i = m + 1 n + 1 ( i m + 1 ) = ∑ i = m n ( i m + 1 ) + ( i m ) = ( n + 1 n − m ) + ( n + 1 n − m − 1 ) = ( n + 2 ( n + 1 ) − ( m + 1 ) )

    引理得证,接下来开始计算自然数幂和。
    i=1nik=i=1nj=1min(i,k)(ij)S(k,j)j!=j=1kS(k,j)j!i=jn(ij)=j=1kS(k,j)j!(n+1nj)=j=1kS(k,j)(n+1)j+1j+1 ∑ i = 1 n i k = ∑ i = 1 n ∑ j = 1 m i n ( i , k ) ( i j ) S ( k , j ) j ! = ∑ j = 1 k S ( k , j ) j ! ∑ i = j n ( i j ) = ∑ j = 1 k S ( k , j ) j ! ( n + 1 n − j ) = ∑ j = 1 k S ( k , j ) ( n + 1 ) j + 1 _ j + 1

    由于 (n+1)j+1 ( n + 1 ) j + 1 _ 是由 j+1 j + 1 个连续整数相乘,必然有一个为 j+1 j + 1 的倍数。因此这种方法可以在 O(k2) O ( k 2 ) 的时间内处理出任何模数下的自然数幂和。如果模数类似于998244353,我们可以先用NTT预处理出所有的第二类斯特林数,再预处理出 n+1 n + 1 的下降幂和正整数逆元,可以在 O(klogk) O ( k l o g k ) 的时间计算出自然数幂和。

    性质应用例题BZOJ2159

    给定一棵树,每条边边权为1,对于每个节点 ui=1ndist(u,i)k u , 求 ∑ i = 1 n d i s t ( u , i ) k
    考虑应用第二类斯特林数的性质

    i=1ndist(u,i)k=i=1nj=1kS(k,j)(dist(u,i)j)j!=j=1kS(k,j)j!i=1n(dist(u,i)j) ∑ i = 1 n d i s t ( u , i ) k = ∑ i = 1 n ∑ j = 1 k S ( k , j ) ( d i s t ( u , i ) j ) j ! = ∑ j = 1 k S ( k , j ) j ! ∑ i = 1 n ( d i s t ( u , i ) j )

    则对于每个节点,都计算出 i=1n(dist(u,i)j) ∑ i = 1 n ( d i s t ( u , i ) j ) 即可。我们分两次进行树形dp,第一次统计每个节点和它子树当中所有点的和,记为 f(u,j)f(u,j)=vson[u]f(v,j1)+f(v,j) f ( u , j ) , 则 f ( u , j ) = ∑ v ∈ s o n [ u ] f ( v , j − 1 ) + f ( v , j ) ,第二次统计每个节点除子树外的所有节点的和,记为 g(u,j)g(u,j)=g(fa[u],j)+g(fa[u],j1)+vson[fa[u]]vuf(v,j2)+2f(v,j1)+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 ) ,后面那个求和预处理一下 s(j)=vson[fa[u]]f(v,j) s ( j ) = ∑ v ∈ s o n [ f a [ u ] ] f ( v , j ) ,计算的时候减去自己即可。总复杂度 O(nk+k2) O ( n k + k 2 )

    反演公式


    g(n)=i=mnS(n,i)f(i) g ( n ) = ∑ i = m n S ( n , i ) f ( i )


    f(n)=i=mn(1)nis(n,i)g(i) f ( n ) = ∑ i = m n ( − 1 ) n − i s ( n , i ) g ( i )

    其中大写 S S 表示第二类斯特林数,小写s表示第一类斯特林数。
    证明:
    i=mn(1)nis(n,i)g(i) ∑ i = m n ( − 1 ) n − i s ( n , i ) g ( i )

    =i=mn(1)nis(n,i)j=miS(i,j)f(j) = ∑ i = m n ( − 1 ) n − i s ( n , i ) ∑ j = m i S ( i , j ) f ( j )

    =j=mnf(j)i=jn(1)nis(n,i)S(i,j) = ∑ j = m n f ( j ) ∑ i = j n ( − 1 ) n − i s ( n , i ) S ( i , j )

    考虑两类斯特林数的性质,有
    xn=i=1n(1)nis(n,i)xi=i=1n(1)nis(n,i)j=1iS(i,j)xj x n _ = ∑ i = 1 n ( − 1 ) n − i s ( n , i ) x i = ∑ i = 1 n ( − 1 ) n − i s ( n , i ) ∑ j = 1 i S ( i , j ) x j _

    =j=1nxji=jn(1)nis(n,i)S(i,j) = ∑ j = 1 n x j _ ∑ i = j n ( − 1 ) n − i s ( n , i ) S ( i , j )

    根据上述等式,我们发现只有当 j=n j = n 时后面算式的值才应当为1,其他时刻全为0.因此:
    i=mn(1)nis(n,i)g(i)=f(n) ∑ i = m n ( − 1 ) n − i s ( n , i ) g ( i ) = f ( n )

    证毕。
    我们其实会发现斯特林反演和二项式反演的形式很像,那二项式反演的第二种形式斯特林反演是否满足呢?满足。
    g(m)=i=mnS(i,m)f(i)f(m)=i=mn(1)ims(i,m)g(i) g ( m ) = ∑ i = m n S ( i , m ) f ( i ) , 则 f ( m ) = ∑ i = m n ( − 1 ) i − m s ( i , m ) g ( i )

    用类似二项式反演的办法可以得到
    i=mn(1)ims(i,m)g(i)=j=mnf(j)i=mj(1)imS(j,i)s(i,m) ∑ i = m n ( − 1 ) i − m s ( i , m ) g ( i ) = ∑ j = m n f ( j ) ∑ i = m j ( − 1 ) i − m S ( j , i ) s ( i , m )

    再次考虑他们的性质,换一种方法可以得到:
    xn=i=1nS(n,i)xi=i=1nS(n,i)j=1i(1)ijs(i,j)xj x n = ∑ i = 1 n S ( n , i ) x i _ = ∑ i = 1 n S ( n , i ) ∑ j = 1 i ( − 1 ) i − j s ( i , j ) x j

    =j=1nxji=jn(1)ijS(n,i)s(i,j) = ∑ j = 1 n x j ∑ i = j n ( − 1 ) i − j S ( n , i ) s ( i , j )

    仍然会有后面的部分为1当且仅当 j=n j = n 。于是把这个性质带入回去,也就是把上式的 j j 变为m n n 变为j,就会发现只有当 j=m j = m 的时候上式的值才为1.因此
    j=mnf(j)i=mj(1)imS(j,i)s(i,m)=f(m) ∑ j = m n f ( j ) ∑ 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)ig(i)ig(i) f ( i ) 为 异 或 图 中 连 通 块 个 数 恰 好 为 i 的 方 案 数 , g ( i ) 为 异 或 图 中 连 通 块 个 数 大 于 等 于 i 的 方 案 数 。 考 虑 怎 么 求 g ( i )

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

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

    于是我们用 O(bell(n)n2s) O ( b e l l ( n ) n 2 s ) 的时间算出了所有的 g g ,接下来算出f即可。

    根据定义,有

    g(m)=i=mnS(i,m)f(i) g ( m ) = ∑ i = m n S ( i , m ) f ( i )
    因为计算的时候我们相当于把 i i 个连通块划分成了m个子集。
    于是根据斯特林反演,我们可以得到
    f(m)=i=mn(1)ims(i,m)g(i) f ( m ) = ∑ i = m n ( − 1 ) i − m s ( i , m ) g ( i )

    于是我们最终可以求出 f(1) f ( 1 ) ,整个问题便解决了。

    展开全文
    WAautomaton 2018-08-04 13:09:07
  • 终于讲到反演定理了,反演定理这种东西记一下公式就好了,反正我是证明不出来的~(~o ̄▽ ̄)~o 首先,著名的反演公式 我先简单的写一下o( ̄ヘ ̄*o) 比如下面这个公式 f(n) = g(1) + g(2) + g(3) ...

    终于讲到反演定理了,反演定理这种东西记一下公式就好了,反正我是证明不出来的~(~o ̄▽ ̄)~o

     

     

     

     

     

     

     

    首先,著名的反演公式

    我先简单的写一下o( ̄ヘ ̄*o)

    比如下面这个公式

    f(n) = g(1) + g(2) + g(3) + ... + g(n)

    如果你知道g(x),蓝后你就可以知道f(n)了

     

    如果我知道f(x),我想求g(n)怎么办

    这个时候,就有反演定理了

    反演定理可以轻松的把上面的公式变为

    g(n) = f(1) + f(2) + f(3) + ... + f(n)

     

    当然,我写的只是个形式,怎么可能这么简单。◕‿◕。

     

    其实每一项再乘一个未知的函数就对了,但是这个函数我们不知道(不用担心,数学家已经帮我们解决了,我们直接用就可以了)

     

     

     

     

     

     

    反演公式登场( >ω<)

     

    反演定理1

     

    c和d是两个跟n和r有关的函数

    根据用法不同,c和d是不同的

    一般数学家会先随便弄c函数

    然后经过复杂的计算和证明,得到d函数

    然后公式就可以套用了

     

     

     

     

     

     

     

     

     

     

     

    正片开始

     

    二项式反演公式

     

    二项式反演1

     

    那个括号起来的就是组合数,我记得组合数那章我有说过

    组合数4

     

     

    二项式反演也就是记住这个公式就算结束了

     

    然后我们开始实战(/ω\)

     

     

     

     

     

     

     

     

     

    容斥那章讲过的全错排(装错信封问题)

    hdu 1465

    http://acm.hdu.edu.cn/showproblem.php?pid=1465

     

     

     

     设g(i)表示正好有i封信装错信封

    那么全部的C(n, i)*g(i)加起来正好就是所有装信的情况,总共n!种情况

    n! = Σ C(n, i)*g(i) (i从0到n)

    那么f(n) = n!,所以f(x) = x!

    那么我们要求g(n)

    根据公式

     

    g(n) = Σ (-1)^(n-i) * C(n, i) * f(i)  (i从0到n)

     

    那么就可以计算啦~\(≧▽≦)/~

     

    AC代码:

    #include<cstdio>
    typedef long long LL;
    int n, flag;
    LL fac[25];
    LL ans;
    void init(){
        fac[0] = 1;
        for(int i = 1; i <= 20; i ++) fac[i] = fac[i-1] * i;    
    }
    int main(){
        init();
        while(~scanf("%d", &n)){
            ans = 0;
            flag = n & 1 ? -1 : 1;//起始符号
            for(int i = 0; i <= n; i ++){
                ans += flag * fac[n] / fac[n-i];
                flag = -flag;  
            }
            printf("%I64d\n", ans);
        }
    }
    View Code

     

    是不是很好用但是不容易想到T_T

    这也没有办法

     

    再来一题吧

    还是容斥那一章讲过的题目的

    UVALive 7040

    https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=5052

     

    题意:给n盆花涂色,从m种颜色中选取k种颜色涂,保证正好用上k种颜色,你必须用上这k种颜色去涂满n个相邻的花,并且要求相邻花的颜色不同,求方案数。

     (1 ≤ n, m ≤ 1e9 , 1 ≤ k ≤ 1e6 , k ≤ n, m)

     

     

     

     

    首先,用k种颜色涂花,假如不考虑全部用上,那么总的方案数是多少

    第一盆花有k种颜色选择,之后的花因为不能跟前一盆花的颜色相同,所以有k-1种选择

    于是总方案数为k*(k-1)^(n-1)

    我们设必须用 i 种颜色两两不相邻的涂花的方案数为 g(i)

    那么

    k*(k-1)^(n-1) = Σ C(k, i)*g(i) (i从1到k)

    令f(k) = k*(k-1)^(n-1),那么f(x) = x*(x-1)^(n-1)

    二项式反演公式出现了

    所以g(k) = Σ (-1)^(k-i) * C(k, i) * f(i)  (i从1到k)

     

     

    最终的答案就是C(m, k) * g(k)

    (这里m有1e9,C(m, k)直接用for循环算,直接for循环从m*(m-1)*...*(m-k+1)再乘k的阶乘的逆元)

     

     

     

     

    AC代码:

    #include<cstdio>
    typedef long long LL;
    const int N = 1000000 + 5;
    const int MOD = (int)1e9 + 7;
    int F[N], Finv[N], inv[N];
    LL pow_mod(LL a, LL b, LL p){ 
        LL ret = 1;
        while(b){
            if(b & 1) ret = (ret * a) % p;
            a = (a * a) % p;
            b >>= 1;
        }
        return ret;
    }
    void init(){
        inv[1] = 1;
        for(int i = 2; i < N; i ++){
            inv[i] = (MOD - MOD / i) * 1ll * inv[MOD % i] % MOD;
        }
        F[0] = Finv[0] = 1;
        for(int i = 1; i < N; i ++){
            F[i] = F[i-1] * 1ll * i % MOD;
            Finv[i] = Finv[i-1] * 1ll * inv[i] % MOD;
        }
    }
    int comb(int n, int m){
        if(m < 0 || m > n) return 0;
        return F[n] * 1ll * Finv[n - m] % MOD * Finv[m] % MOD;
    }
    int main(){
        init();
        int T, n, m, k, ans, flag, temp;
        scanf("%d", &T);
        for(int cas = 1; cas <= T; cas ++){
            scanf("%d%d%d", &n, &m, &k);
            ans = 0;
            flag = (k & 1) ? 1 : -1;
            //计算g(k) 
            for(int i = 1; i <= k; i ++){
                ans = (ans + 1ll * flag * comb(k, i) * i % MOD * pow_mod(i-1, n-1, MOD) % MOD) % MOD;
                flag = -flag;
            }
            //接下来计算C(m, k) 
            temp = Finv[k];
            for(int i = 1; i <= k; i ++){
                temp = 1ll * temp * (m-k+i) % MOD;
            }
            ans = ((1ll * ans * temp) % MOD + MOD) % MOD;
            printf("Case #%d: %d\n", cas, ans);
        }
    }
    View Code

     

     

    做完两题之后就感觉二项式反演变得容易了,遇到题目还是要多想( ̄▽ ̄")

    等等。。。做完两题的我突然发现二项式反演和容斥推倒出来的公式总是一样的。。。。。。(为什么有种被骗的感觉T_T)

    转载于:https://www.cnblogs.com/xzxl/p/7354141.html

    展开全文
    weixin_33978044 2017-08-13 17:44:00
  • 2KB qq_30117177 2019-09-22 13:34:03
  • 莫比乌斯反演定理形式一: F ( n ) = ∑ d | n f ( d ) = > f ( n ) = ∑ d | n μ ( d ) F ( n d ) F(n)=\sum_{d|n}f(d)=>f(n)=\sum_{d|n}\mu(d)F(\frac{n}{d}) 证明: 恒等变形得: f ( n ) = ∑ d | n ...

    PoPoQQQ没有给出形式二的证明,我恨PoPoQQQ,证了好久。
    证明之前,请先看看PoPoQQQ的ppt,当你看完发现没有证明想哭的时候,看看这篇博客。
    莫比乌斯反演定理形式一:

    F(n)=d|nf(d)=>f(n)=d|nμ(d)F(nd)

    证明:
    恒等变形得:
    f(n)=d|nμ(d)F(nd)=d|nμ(d)k|ndf(k)=k|nf(k)d|nkμ(d)

    因为之前证明的这个定理:

    d|nμ(d)={10n==1n>1

    所以当且仅当 nk=1 ,即n=k时, d|nkμ(d)=1 ,其余时候等于0。

    k|nf(k)d|nkμ(d)=f(n)

    莫比乌斯反演定理形式二:

    F(n)=n|df(d)=>f(n)=n|dμ(dn)F(d)

    证明:
    k=dn ,那么,就得到
    f(n)=k=1+μ(k)F(nk)=k=1+μ(k)nk|tf(t)=n|tf(t)k|tnμ(k)

    所以当且仅当 tn=1 ,即t=n时, k|tnμ(k)=1 ,其余时候等于0。
    故得到
    n|tf(t)k|tnμ(k)=f(n)

    证明完毕。

    展开全文
    outer_form 2016-01-26 16:38:33
  • 近期学习了莫比乌斯反演,算是一个学习笔记吧… 在这里首先要说明: 1:本文讨论的所有函数为数论函数,即定义域为D=N∗D=N^*D=N∗的函数; 2:∑d∣nf(d)\sum \limits_{d|n}f(d)d∣n∑​f(d)表示ddd取遍nnn的...

    近期学习了莫比乌斯反演,算是一个学习笔记吧…

    在这里首先要说明:

    1:本文讨论的所有函数为数论函数,即定义域为 D = N ∗ D=N^* D=N的函数;

    2: ∑ d ∣ n f ( d ) \sum \limits_{d|n}f(d) dnf(d)表示 d d d取遍 n n n的所有正因子,再将所有的 f ( d ) f(d) f(d)相加,例如当 n = 6 n=6 n=6时, ∑ d ∣ n f ( d ) = f ( 1 ) + f ( 2 ) + f ( 3 ) + f ( 6 ) \sum \limits_{d|n}f(d)=f(1)+f(2)+f(3)+f(6) dnf(d)=f(1)+f(2)+f(3)+f(6)

    3: ∏ i = 1 k a i = a 1 × a 2 × . . . × a k \prod \limits_{i=1}^ka_i=a_1 \times a_2 \times ... \times a_k i=1kai=a1×a2×...×ak,即所有 a i a_i ai的乘积;

    4: [ p ] [p] [p](其中p是一个表达式)表示当p成立时,值为1;否则值为0;

    5: ( a , b ) (a,b) (a,b)表示 g c d ( a , b ) gcd(a,b) gcd(a,b),即 a , b a,b a,b的最大公因数;

    6:几个在狄利克雷卷积中会出现的基本函数:

    • ε ( n ) = [ n = 1 ] \varepsilon(n)=[n=1] ε(n)=[n=1],也就是 ε ( n ) = { 1 n = 1 0 n ≠ 1 \varepsilon(n)=\begin{cases}1\qquad n=1\\0 \qquad n \neq 1 \end{cases} ε(n)={1n=10n̸=1
    • I ( n ) = 1 I(n)=1 I(n)=1
    • i d ( n ) = n id(n)=n id(n)=n

    一、积性函数

    定义:如果一个函数 f ( n ) f(n) f(n)满足:当 ( a , b ) = 1 (a,b)=1 (a,b)=1时,有 f ( a b ) = f ( a ) × f ( b ) f(ab)=f(a) \times f(b) f(ab)=f(a)×f(b),则称 f ( n ) f(n) f(n)为积性函数。

    进一步,如果对于任意数 a , b a,b a,b,都有 f ( a b ) = f ( a ) × f ( b ) f(ab)=f(a) \times f(b) f(ab)=f(a)×f(b),则称 f ( n ) f(n) f(n)为完全积性函数。

    积性函数的基本性质:对于任意正整数 n ≠ 1 n \neq 1 n̸=1,根据唯一分解定理,可以进行分解素因数:即 n = p 1 c 1 . . . p k c k = ∏ i = 1 k p i c i n=p_1^{c_1}...p_k^{c_k}=\prod \limits_{i=1}^kp_i^{c_i} n=p1c1...pkck=i=1kpici,显然所有的 p i c i p_i^{c_i} pici两两互素,因此有:

    f ( n ) = f ( p 1 c 1 ) × . . . × f ( p k c k ) = ∏ i = 1 k f ( p i c i ) f(n)=f(p_1^{c_1}) \times ... \times f(p_k^{c_k})=\prod \limits_{i=1}^kf(p_i^{c_i}) f(n)=f(p1c1)×...×f(pkck)=i=1kf(pici)

    因此,我们可以用类似线性筛素数的方法线性筛出某一积性函数的值,只需要知道对于每一个素数以及素数的方幂结果为多少即可。

    由积性函数以及完全积性函数的定义, ε ( n ) , I ( n ) , i d ( n ) \varepsilon(n),I(n),id(n) ε(n),I(n),id(n)显然皆为完全积性函数。

    证明积性函数的常见方法是利用上面的唯一分解式,将 a , b a,b a,b唯一分解,再用 ( a , b ) = 1 (a,b)=1 (a,b)=1的条件可以得到分解出来的所有素数两两不等,从而继续证明。

    例如:证明 d ( n ) d(n) d(n) n n n的正因子个数为积性函数。

    证明:取 ( a , b ) = 1 (a,b)=1 (a,b)=1,将 a , b a,b a,b分解得: a = ∏ i = 1 k p i c i a=\prod \limits_{i=1}^kp_i^{c_i} a=i=1kpici,且 b = ∏ i = 1 l q i d i b=\prod \limits_{i=1}^lq_i^{d_i} b=i=1lqidi,则 p i , q i p_i,q_i pi,qi两两不等(由 ( a , b ) = 1 (a,b)=1 (a,b)=1可得),于是:
    d ( a ) = ∏ i = 1 k ( c i + 1 ) d(a)=\prod \limits_{i=1}^k(c_i+1) d(a)=i=1k(ci+1),且 d ( b ) = ∏ i = 1 l ( d i + 1 ) d(b)=\prod \limits_{i=1}^l(d_i+1) d(b)=i=1l(di+1)
    由于 p i , q i p_i,q_i pi,qi两两不等,所以 d ( a b ) = ∏ i = 1 k ( c i + 1 ) ∏ i = 1 l ( d i + 1 ) = d ( a ) × d ( b ) d(ab)=\prod \limits_{i=1}^k(c_i+1)\prod \limits_{i=1}^l(d_i+1)=d(a) \times d(b) d(ab)=i=1k(ci+1)i=1l(di+1)=d(a)×d(b),即 d ( n ) d(n) d(n)是积性函数。

    *积性函数另一个不太常用的性质:若 f ( n ) f(n) f(n)是积性函数,则或者 f ( n ) f(n) f(n)是值为 0 0 0的常值函数,或者 f ( 1 ) = 1 f(1)=1 f(1)=1

    证明十分容易,因为 ( n , 1 ) = 1 (n,1)=1 (n,1)=1,所以 f ( n ) = f ( 1 ) × f ( n ) f(n)=f(1) \times f(n) f(n)=f(1)×f(n),则 f ( n ) = 0 f(n)=0 f(n)=0或者 f ( 1 ) = 1 f(1)=1 f(1)=1

    二、莫比乌斯函数

    定义:若将 n n n分解素因数为 n = p 1 c 1 . . . p k c k = ∏ i = 1 k p i c i n=p_1^{c_1}...p_k^{c_k}=\prod \limits_{i=1}^kp_i^{c_i} n=p1c1...pkck=i=1kpici,则莫比乌斯函数定义为:

    μ ( n ) = { 1 n = 1 ( − 1 ) k c 1 = . . . = c k = 1 0 m a x ( c 1 , . . . , c k ) &gt; 1 \mu(n)=\begin{cases}1\qquad\qquad n=1\\ (-1)^k\qquad c_1=...=c_k=1\\ 0 \qquad\qquad max(c_1,...,c_k)&gt;1\end{cases} μ(n)=1n=1(1)kc1=...=ck=10max(c1,...,ck)>1

    (最后一行的表示其实等价于:若 n n n有一个因子为完全平方数,则 μ ( n ) = 0 \mu (n)=0 μ(n)=0

    莫比乌斯函数是积性函数。

    证明:取 ( a , b ) = 1 (a,b)=1 (a,b)=1,对 a , b a,b a,b进行讨论:

    • a = 1 a=1 a=1 b = 1 b=1 b=1,不妨设 a = 1 a=1 a=1,则 μ ( a ) = 1 \mu(a)=1 μ(a)=1,因为 μ ( b ) = μ ( b ) \mu(b)=\mu(b) μ(b)=μ(b),所以 μ ( a b ) = μ ( a ) × μ ( b ) \mu(ab)=\mu(a) \times \mu(b) μ(ab)=μ(a)×μ(b)
    • μ ( a ) = 0 \mu(a)=0 μ(a)=0 μ ( b ) = 0 \mu(b)=0 μ(b)=0,不妨设 μ ( a ) = 0 \mu(a)=0 μ(a)=0,则存在 p 2 ∣ a p^2|a p2a,所以 p 2 ∣ a b p^2|ab p2ab,所以有 μ ( a b ) = 0 \mu(ab)=0 μ(ab)=0,所以 μ ( a b ) = μ ( a ) × μ ( b ) \mu(ab)=\mu(a) \times \mu(b) μ(ab)=μ(a)×μ(b)
    • 否则,设 a = p 1 p 2 . . . p k , b = q 1 q 2 . . . q l a=p_1p_2...p_k,b=q_1q_2...q_l a=p1p2...pkb=q1q2...ql,则 μ ( a ) = ( − 1 ) k , μ ( b ) = ( − 1 ) l \mu(a)=(-1)^k,\mu(b)=(-1)^l μ(a)=(1)kμ(b)=(1)l,因为 ( a , b ) = 1 (a,b)=1 (a,b)=1,所以 p i , q i p_i,q_i pi,qi两两不等,因此 μ ( a b ) = ( − 1 ) k + l \mu(ab)=(-1)^{k+l} μ(ab)=(1)k+l,所以: μ ( a b ) = μ ( a ) × μ ( b ) \mu(ab)=\mu(a) \times \mu(b) μ(ab)=μ(a)×μ(b)

    综上所述, μ ( a b ) = μ ( a ) × μ ( b ) \mu(ab)=\mu(a) \times \mu(b) μ(ab)=μ(a)×μ(b),所以 μ ( n ) \mu(n) μ(n)是积性函数。

    前面已经提到,积性函数可以用线性筛的方法筛出,下面就是使用线性筛求 μ ( 1 ) \mu(1) μ(1) μ ( x ) \mu(x) μ(x)的代码,关键部分有注释:

    void init (int x) {
    	mob[1]=1;    //由定义可得mob[1]=1
    	for (int i=2;i<=x;i++) {
    		if (!p[i]) {
    			n[++cnt]=i;
    			mob[i]=-1;    //若i是素数,则mob[i]=(-1)^1=-1
    		}
    		for (int j=1;j<=cnt;j++) {
    			p[i*n[j]]=1;
    			if (i%n[j]==0) {    //若i是n[j]的倍数
    				mob[i*n[j]]=0;    //则i*n[j]有n[j]^2的平方因数,所以函数值为0
    				break;
    			} else {
    				mob[i*n[j]]=-mob[i];    //i*n[j]多了素因子n[j],-1的次数加1
    			}
    		}
    	}
    }
    

    下面是一个莫比乌斯函数的重要性质,也是莫比乌斯反演定理的核心内容:

    ∑ d ∣ n μ ( n ) = [ n = 1 ] \sum \limits_{d|n}\mu(n)=[n=1] dnμ(n)=[n=1]

    证明:

    • n = 1 n=1 n=1,则上式的值为 μ ( n ) = 1 \mu(n)=1 μ(n)=1,成立;

    • 否则,设 n n n k k k个不同的素因子,则只需考虑这些素因子的组合即可(因为一旦某个素因子的个数大于1,则结果为0,不计入求和答案);那么取奇数个素因数时,莫比乌斯函数的值为-1,取偶数个素因数时,莫比乌斯函数的值为1,因此原式可转化为:
      C n 0 − C n 1 + . . . + ( − 1 ) n C n n C_n^0-C_n^1+...+(-1)^nC_n^n Cn0Cn1+...+(1)nCnn

    • 再由于 C n m = C n − 1 m − 1 + C n − 1 m ( 0 &lt; m &lt; n ) C_n^m=C_{n-1}^{m-1}+C_{n-1}^m\quad(0&lt;m&lt;n) Cnm=Cn1m1+Cn1m(0<m<n),因此原式可以化为:

    C n 0 − C n − 1 0 − C n − 1 1 + . . . + ( − 1 ) n − 1 C n − 1 n − 2 + ( − 1 ) n − 1 C n − 1 n − 1 + ( − 1 ) n C n n C_n^0-C_{n-1}^0-C_{n-1}^1+...+(-1)^{n-1}C_{n-1}^{n-2}+(-1)^{n-1}C_{n-1}^{n-1}+(-1)^nC_n^n Cn0Cn10Cn11+...+(1)n1Cn1n2+