复习笔记——一些反演

莫比乌斯反演

莫比乌斯函数

( egin{equation} mu(x)= egin{cases} 1& x=1\ 0& x含有平方因子\ (-1)^k& x有k个质因子 end{cases} end{equation} )

是积性函数，可以用线性筛求

int mu[N],p[N],prime[N],pnum;
void getp(){
    for(int i=1;i<N;i++) p[i]=1;
    mu[1]=1;
    for(int i=2;i<N;i++){
        if(p[i]) prime[pnum++]=i,mu[i]=-1;
        for(int j=0;j<pnum && 1ll*i*prime[j]<N;j++){
            p[i*prime[j]]=0;
            if(i%prime[j]==0){
                mu[i*prime[j]]=0;
                break;
            }
            mu[i*prime[j]]=-mu[i];
        }
    }
}

反演

若 (f(x)=sumlimits_{d|x} g(d))，则 (g(x)=sumlimits_{d|x} mu(frac{x}{d}) f(d))
若 (f(x)=sumlimits_{x|d} g(d))，则 (g(x)=sumlimits_{x|d} mu(frac{d}{x}) f(d))

应用

与 (gcd) 相关的：要求对 (gcd=k) 的计数，转而对 (gcd) 为 (k) 的倍数的计数
与约数个数相关：(d(n)) 表示 (n) 的约数个数，则 (d(xy)=sumlimits_{i|x}sumlimits_{j|y} [gcd(i,j)==1])
(gcd(x,y)=sumlimits_{d|x,d|y} phi(d))：证明——狄利克雷卷积 (phi * I=id)，而满足 (d|x,d|y) 的满足 (d|gcd(x,y))

二项式反演

反演

若 (f(n)=sumlimits_{i=0}^n (-1)^iinom{n}{i} g(i)) ，则 (g(n)=sumlimits_{i=0}^n (-1)^iinom{n}{i} f(i)) （极其对称）
若 (f(n)=sumlimits_{i=0}^n inom{n}{i} g(i)) ，则 (g(n)=sumlimits_{i=0}^n (-1)^{n-i} inom{n}{i} f(i))
若 (f(n)=sumlimits_{i=n}^m inom{i}{n} g(i)) ，则 (g(n)=sumlimits_{i=n}^m (-1)^{i-n} inom{i}{n} f(i))

应用

由至少 (Rightarrow) 恰好，用第二个式子
由至多 (Rightarrow) 恰好，用第三个式子

Min-Max反演

反演

对于集合 (S)
(minS=sumlimits_{T subseteq S} (-1)^{|T|-1} maxT)
(maxS=sumlimits_{T subseteq S} (-1)^{|T|-1} minT)

(min) 与 (max) 的期望也是满足这个式子的

应用

比较经典的问题是抽卡片，求都抽到的期望

(max(S)) 表示卡片集合 (S) 中最后抽到卡第一次抽到的期望时间， (min(S)) 表示第一个抽到的卡第一次抽到的期望时间
(max(S)=sumlimits_{Tsubseteq S} (-1)^{|T|-1} min(T))
而 (min(T)=frac{1}{sumlimits_{iin T}p_i})

子集反演

反演

(f(S)=sumlimits_{Tsubseteq S} g(T))，则 (g(S)=sumlimits_{Tsubseteq S} (-1)^{|S|-|T|} f(T))

应用

在 (FWT) 中会用到
尤其是自己手推的时候应该知道这个式子