快速莫比乌斯变换 (Fast Mobius Transform, FMT)

子集反演

莫比乌斯变换

[f(S)=sum_{Tsubseteq S} g(T) ]

莫比乌斯反演

[g(S)=sum_{Tsubseteq S}(-1)^{|S|-|T|} f(T) ]

证明：
由

[sum_{i=0}^n(-1)^{i}inom{n}{i}=[n=0] ]

可得

[sum_{Tsubseteq S} (-1)^{|T|}=[S=phi] ]

[g(S)=sum_{Tsubseteq S} [S-T=phi] g(T)\ =sum_{Tsubseteq S}sum_{Psubseteq S-T} (-1)^{|P|} g(T)\ =sum_{Psubseteq S}sum_{Tsubseteq S-P} (-1)^{|P|} g(T)\ =sum_{Psubseteq S}(-1)^{|P|}sum_{Tsubseteq S-P} g(T)\ =sum_{Psubseteq S}(-1)^{|P|}f(S-P)\ =sum_{Tsubseteq S} (-1)^{|S|-|T|} f(T) ]

证毕。

合并卷积

定义

[h(S)=f(S)*g(S)=sum_{Asubseteq S}sum_{Bsubseteq S} f(A)g(B)[Acup B=S] ]

称 (h) 是 (f) 和 (g) 的合并卷积。

设 (hat h(S)) 是 (h(S)) 的莫比乌斯变换，则

[hat h(S)=sum_{Tsubseteq S}sum_{Asubseteq T}sum_{Bsubseteq T} f(A)g(B)[Acup B=T]\ =sum_{Asubseteq S}sum_{Bsubseteq S} f(A)g(B)[Acup Bsubseteq S]\ =sum_{Asubseteq S}sum_{Bsubseteq S} f(A)g(B)\ =sum_{Asubseteq S}f(A)sum_{Bsubseteq S} g(B)\ =hat f(S)hat g(S) ]

这启发我们计算 (f) 和 (g) 的合并卷积时，可以先将 (f) 和 (g) 分别做莫比乌斯变换，然后相乘，得到 (h) 的莫比乌斯变换 (hat h)，再对 (hat h) 做莫比乌斯反演，即得到 (f) 和 (g) 的合并卷积 (h)。

快速莫比乌斯变换 (Fast Möbius Transform, FMT)

要求

[hat f(S)=sum_{Tsubseteq S} f(T) ]

定义 (hat f(S,i)=sum_{Tsubseteq S}f(T)[{i+1,i+2,dots,n}subseteq T])，
那么有 (hat f(S,0)=f(S))，(hat f(S,|S|)=f(phi))。
设集合 (Scap {i}=phi)，

那么 (hat f(Scup {i},i)=hat f(S,i-1)+hat f(Scup{i},i-1))
因为 (Scap {i}=phi)，所以 (hat f(S,i)=hat f(S,i-1))
(hat f(S,i))表示 ({i+1,i+2,dots,n}) 一定含于 (T)，并且一定没有选 (i)，
(hat f(Scup{i},i-1)) 表示 ({i+1,i+2,dots,n}) 一定含于 (T)，并且一定选了 (i)，
那么由加法原理即可知 (hat f(Scup {i},i)=hat f(S,i-1)+hat f(Scup{i},i-1))。
那么我们递推 (n) 轮，即可求得 (hat f(S))。
时间复杂度 (O(n2^n))。

void FMT(int *f){
    for(int i=0;i<n;++i)
        for(int j=0;j<(1<<n);++j)
            if(j&(1<<i)) f[j]+=f[j^(1<<i)];
}

快速莫比乌斯反演 (IFMT)

跟FMT一样，不断递推，不过变成了减法。

void IFMT(int *f){
    for(int i=0;i<n;++i)
        for(int j=0;j<(1<<n);++j)
            if(j&(1<<i)) f[j]-=f[j^(1<<i)];
}

子集卷积

定义

[h(S)=f(S)*g(S)=sum_{Asubseteq S}sum_{Bsubseteq S} f(S)g(S)[Acup B=S][Acap B=phi]\ =sum_{Tsubseteq S} f(T)g(S-T) ]

称 (h) 是 (f) 和 (g) 的子集卷积。

因为子集卷积和之前的合并卷积不同，要求 (Acup B=S, Acap B=phi)，那么设 (f(i,S)) 表示集合 (S) 有 (i) 个元素时的 (f(S))，那么只有 (f(|S|,S)) 才是正确的。先对 (f) 和 (g) 做FMT，然后对做完FMT的 (f(i,S)) 和 (g(j,S)) 进行暴力卷积，有 (h(i+j,S)=sum_{i,j} f(i,S)*g(j,S))。最后再进行一次 IFMT，即可求出子集卷积。时间复杂度 (O(n^22^n))。

Code (洛谷 P6097)

#include <bits/stdc++.h>
using namespace std;

#define RG register int
#define LL long long

template<typename elemType>
inline void Read(elemType &T){
    elemType X=0,w=0; char ch=0;
    while(!isdigit(ch)) {w|=ch=='-';ch=getchar();}
    while(isdigit(ch)) X=(X<<3)+(X<<1)+(ch^48),ch=getchar();
    T=(w?-X:X);
}

#define bitcnt(x) __builtin_popcount(x)
const LL MOD=1000000009LL;
int A[1<<21],B[1<<21];  
int a[21][1<<21],b[21][1<<21],c[21][1<<21];
int n,len;

void FMT(int *f,int n){
    for(RG i=0;i<n;++i)
        for(RG j=0;j<(1<<n);++j)
            if(j&(1<<i)) f[j]=(f[j]+f[j^(1<<i)])%MOD;
}
void IFMT(int *f,int n){
    for(RG i=0;i<n;++i)
        for(RG j=0;j<(1<<n);++j)
            if(j&(1<<i)) f[j]=((f[j]-f[j^(1<<i)])%MOD+MOD)%MOD;
}

void Convolution(int n){
    for(RG x=0;x<=n;++x){
        for(RG i=0;i<=x;++i)
            for(RG s=0;s<(1<<n);++s)
                c[x][s]=(1LL*c[x][s]+1LL*a[i][s]*b[x-i][s]%MOD)%MOD;
        IFMT(c[x],n);
    }
}

int main(){
    Read(n);len=1<<n;
    for(RG i=0;i<len;++i){
        Read(A[i]);
        a[bitcnt(i)][i]=A[i];
    }
    for(RG i=0;i<len;++i){
        Read(B[i]);
        b[bitcnt(i)][i]=B[i];
    }
    for(RG i=0;i<=n;++i){
        FMT(a[i],n);
        FMT(b[i],n);
    }
    Convolution(n);
    for(RG i=0;i<len;++i)
        printf("%d ",c[bitcnt(i)][i]);

    return 0;
}

另一份模板

namespace FMT{
    #define bitcnt(x) __builtin_popcount(x)
    const int MOD=998244353LL;
    const int Base=21;

    inline int mo(int x){
        if(x>=MOD) x-=MOD;
        if(x<0) x+=MOD;
        return x;
    }
    inline int mul(int x,int y){return 1LL*x*y%MOD;}

    void FMT(vector<int> &f,int n=Base){
        int len=1<<n;
        for(RG i=0;i<n;++i)
            for(RG j=0;j<len;++j)
                if(j&(1<<i)) f[j]=mo(f[j]+f[j^(1<<i)]);
    }
    void IFMT(vector<int> &f,int n=Base){
        int len=1<<n;
        for(RG i=0;i<n;++i)
            for(RG j=0;j<len;++j)
                if(j&(1<<i)) f[j]=mo(f[j]-f[j^(1<<i)]);
    }

    vector<int> subset_convolution(vector<int> &A,vector<int> &B,int n=Base){
        int len=1<<n;
        vector<int> H(len);
        vector<vector<int> > sH(n+1,vector<int>(len,0)),sA=sH,sB=sH;
        for(RG s=0;s<len;++s){
            sA[bitcnt(s)][s]=A[s];
            sB[bitcnt(s)][s]=B[s];
        }
        for(RG i=0;i<=n;++i){
            FMT(sA[i],n);
            FMT(sB[i],n);
            for(RG s=0;s<len;++s)
                for(RG j=0;j<=i;++j)
                    sH[i][s]=mo(sH[i][s]+mul(sA[j][s],sB[i-j][s]));
            IFMT(sH[i],n);
        }
        for(RG s=0;s<len;++s)
            H[s]=sH[bitcnt(s)][s];
        return H;
    }
};