反演魔术

· · 个人记录

炫酷反演魔术

二项式反演：

预备条件：

0=(1+(-1-)^n=\sum \limits_{k=0}^n(-1)^k*C(n,k)

f(n):n个人随便排的方案数，g(n):n个人都排错的方案数

f(n)=\sum \limits_{k=0}^nC(n,k)g(k)

结论：

g(n)=\sum \limits_{k=0}^nC(n,k)f(k)

证明：

g(n)=\sum \limits_{m=0}^n[n-m=0]C(n,m)g(m) =\sum \limits_{m=0}^n\sum \limits_{k=0}^{n-m} (-1)^kC(n-m,k)C(n,m)g(m) =\sum \limits_{m=0}^n\sum \limits_{k=0}^{n-m}(-1)^kC(n,k)C(n-k,m)g(m) =\sum \limits_{k=0}^n\sum \limits_{m=0}^{n-m}(-1)^kC(n,k)C(n-k,m)g(m) =\sum \limits_{k=0}^n(-1)^kC(n,k)\sum \limits_{m=0}^{n-k}C(n-k,m)g(m) =\sum \limits_{k=0}^n(-1)^kC(n,k)f(n-k) =\sum \limits_{k=0}^n(-1)^{n-k}C(n,k)f(k)

莫比乌斯反演：

f(n):长为n的小写字母串的方案数，g(n):长度为n，且循环周期为n（不存在一个真子串，使仅用该子串自己拼接即可拼出原串）

f(n)=∑g(d)(n%d==0)

g(n)=∑μ(n/d)f(d)(n%d==0)

(μ为莫比乌斯函数）：μ(n)=

1 (n=1)

(-1)^k n=p1p2……*pk

0 不存在一个pi^2为n的因子

pi为质数