快速沃尔什变换

下面只讨论异或的沃尔什变换。（与和或还是比较naive的）

$h,f,s$ 都是集合到数的映射， $2^U$ 表示全集的所有子集构成的集合。（论文中下面的 $\in$ 都用的是 $\subseteq$ ，其实我觉得应该用 $\in$ ）（集合幂级数的概念还是看论文吧qwq）

h_S=\sum_{L\in 2^U}\sum_{R\in 2^U}[L\oplus R=S]f_Lg_R

有一个性质：

\frac{1}{2^n}\sum_{T\in 2^U}(-1)^{|S\cap T|}=[S=\varnothing]

这个性质空集时显然，非空时可以构造映射使得每个1与-1一一抵消，故成立。
把这个式子代到卷积的定义式中即可推出

h_S=\frac{1}{2^n}\sum_{T\in 2^U}(-1)^{|T\cap S|}(\sum_{L\in 2^U}(-1)^{|T\cap L|}f_L)(\sum_{R\in 2^U}(-1)^{|T\cap R|}g_R)

然后就启发我们沃尔什变换。对 $f$ 定义一个 $f'$ 为 $f$ 的沃尔什变换。

f'_S=\sum_{T\in 2^U}(-1)^{|T\cap S|}f_T

然后对 $f$ 和 $g$ 求出沃尔什变换再对应位相乘再逆变换回去就好了。
根据定义式随便推敲一下就知道代码怎么写了，而且大家都会背233。
然后就是一个比较重要的性质。发现 $f$ 的每一位在 $f'$ 中都有贡献，要么系数为1要么系数为-1。
然后就有一个题

UOJ310 黎明前的巧克力

有一些数，每个数可以分配到A集合，也可以分配到B集合，也可以不分配。
求使得A集合异或和等于B集合异或和的方案数。

首先发现集合A和集合B什么的都是唬人的，一个元素只有选和不选两种状态，选的系数为2（因为可以塞进不同的集合）。

然后就有一种感觉可以生成函数的感觉。。
每一个数有一个对应的集合幂级数，空集的系数为 $1$ ，这个数对应集合的系数为 $2$ ，表示它选还是不选，然后把所有数的集合幂级数乘起来之后取空集对应的系数即可。其中乘法定义为异或。
发现这样需要做 $n$ 次FWT，显然会炸。考虑它有什么特殊性质。发现每个级数中有系数的项极少。
那么考虑上面提到的性质， $f$ 的每一位在 $f'$ 中都有贡献，要么系数为1要么系数为-1。
然后 $f$ 的空集位对所有位的贡献系数都为1。所以每个 $f'$ 的位要么为 $-1$ 要么为 $3$ 。（这一位上+2还是-2）
于是我们只要对一位求出 $\sum f'$ ，就可以通过解方程求出 $\prod f'$ （鸡兔同笼？？）。
$\sum f'$ 是很好求的，因为FWT为线性变换，所以我们把所有对应系数相加，做一次FWT即可。最后再逆FWT回去取出空集位即可。
有一个trick可以把常数除二：我们发现不用做逆FWT。因为我们只需要求出 $f_\varnothing$ 。推一波式子：

\sum_{S\in2^U}f'_S=\sum_{S\in2^U}\sum_{T\in2^U}(-1)^{|T\cap S|}f_T=\sum_{T\in2^U}f_T\sum_{S\in2^U}(-1)^{|T\cap S|}=\sum_{T\in2^U}f_T2^n[T=\varnothing]=2^nf_\varnothing

于是只需把 $f'$ 的所有位加起来再乘一个逆元即可。

子集卷积

是这样的式子：

h_S=\sum_{T\subseteq S}f_Tg_{T\oplus S}

然后可以发现

h_S=\sum_{L\in2^U}\sum_{R\in2^U}[L\cup R=S][|L|+|R|=|S|]f_Lg_R

于是我们加上集合大小的限制之后就变成了集合并卷积。
懒得写了，贴上州区划分的代码得了。。

#include<bits/stdc++.h>
using namespace std;
const int N=3e6+50,M=25,mod=998244353;
int n,m,p,g[N],to[M],mx,sz[N],s[N],is[N],w[N],f[M][N],h[M][N];
int power(int x,int y=p){
    int z=1;
    for(;y;y>>=1,x=1ll*x*x%mod)
        if(y&1)z=1ll*z*x%mod;
    return z;
}
void FWT(int *a,int op){
    for(int i=1;i<mx;i<<=1)
        for(int t=i<<1,j=0;j<mx;j+=t)
            for(int k=0;k<i;k++)
                (a[i+j+k]+=op*a[j+k])%=mod;
}
int main(){
    scanf("%d%d%d",&n,&m,&p);mx=1<<n;
    for(int i=0,x,y;i<m;i++){
        scanf("%d%d",&x,&y),x--,y--,
        to[x]|=1<<y,to[y]|=1<<x;
    }
    for(int i=0;i<n;i++)scanf("%d",&w[i]);
    for(int i=1;i<mx;i++)sz[i]=sz[i>>1]+(i&1);
    for(int i=1;i<mx;i++){
        if(sz[i]==1){g[i]=1;continue;}
        for(int j=0;j<n;j++)if(i>>j&1)
            g[i]|=g[i^1<<j]&&(to[j]&(i^1<<j));
    }
    for(int i=1;i<mx;i++){
        for(int j=0;j<n;j++)if(i>>j&1)
            g[i]&=!(sz[to[j]&(i^1<<j)]&1),s[i]+=w[j];
        s[i]=power(s[i]),is[i]=power(s[i],mod-2);
        if(!g[i])h[sz[i]][i]=s[i];
    }
    for(int i=0;i<mx;i++)f[0][i]=1;
    for(int i=1;i<=n;i++){
        FWT(h[i],1);
        for(int j=1;j<=i;j++){
            for(int k=0;k<mx;k++)
                f[i][k]=(f[i][k]+1ll*f[i-j][k]*h[j][k])%mod;
        }
        FWT(f[i],-1);
        for(int j=0;j<mx;j++)f[i][j]=1ll*f[i][j]*is[j]%mod;
        if(i!=n)FWT(f[i],1);
    }
    printf("%d\n",(f[n][mx-1]+mod)%mod);
    return 0;
}

有一个黎明前的巧克力的严格加强版：
有 $n$ 个数，每个数 $a_i$ 有一个 $b_i$ 的价值。一个位置集合 $\{p\}$ 的价值为 $\prod_{i\in p}b_i$ 。
求满足 $xor_{i\in p}a_i=0$ 的所有位置集合 $p$ 的价值之和。
这个题目相当于把黎明前的巧克中那个权值都为2的特殊性质去掉了，变成了更一般的问题。这需要我们更进一步的分析。
首先还是把这些数都看作集合幂级数生成函数，想要求的就是把这些幂级数相乘之后的空集位。因为这些幂级数还是都满足空集位为 $1$ ，其他某一位为 $b_i$ ，那么它的FWT形式仍然满足我们之前讨论过的形式，即每一位只可能有两种取值，为 $1+b_i$ 或 $1-b_i$ ，取决与这一位与 $a_i$ 交集大小的奇偶性。
设 $f_i[0]=1+b_i,f_i[1]=1-b_i$ 。
那么这些所有FWT形式乘起来的结果就满足：

h_S=\prod_{i=1}^nf_i[|S\cap a_i|\%2]

即

h_S=\prod_{T\in 2^U}\prod_{a_i=T}f_i[|S\cap T|\%2]

惊奇地发现这与FWT变换的形式十分像，都是每一位造成的贡献与交集奇偶性有关。
那么我们对于所有的 $S$ 处理出 $F_S[0]=\prod_{a_i=S}f_i[0]$ 和 $F_S[1]=\prod_{a_i=S}f_i[1]$ 之后就变成了

h_S=\prod_{T\in2^U}F_T[|S\cap T|\%2]

这时再套一下FWT板子就好了。这题是牛客挑战赛36G。

#include<bits/stdc++.h>
using namespace std;
const int N=1<<17,mod=998244353,inv=998236737,M=1<<15;
int n,even[N],odd[N],ans;
char buf[M],*ie=buf+M,*ip=ie-1;
#define G ++ip==ie&&fread(ip=buf,1,M,stdin)
int read(){
    int x=0;G;
    while(!isdigit(*ip))G;
    while(isdigit(*ip))x=x*10+*ip-48,G;
    return x;
}
int main(){
    n=read();
    for(int i=0;i<N;i++)odd[i]=even[i]=1;
    for(int i=1,x,y;i<=n;i++){
        x=read();y=read();
        even[x]=1ll*even[x]*(y+1)%mod;
        odd[x]=1ll*odd[x]*(1-y)%mod;
    }
    for(int i=1;i<N;i<<=1)
        for(int j=0;j<N;j+=i<<1)
            for(int k=0;k<i;k++){
                int a=even[j+k],b=odd[j+k],c=even[i+j+k],d=odd[i+j+k];
                even[j+k]=1ll*a*c%mod;odd[j+k]=1ll*b*d%mod;
                even[i+j+k]=1ll*a*d%mod;odd[i+j+k]=1ll*b*c%mod;
            }
    for(int i=0;i<N;i++)ans=(ans+even[i])%mod;
    printf("%d\n",(1ll*ans*inv%mod-1+mod)%mod);
    return 0;
}

集合幂exp

NOIonline3T3。看洛谷题解大概能看明白。这里要注意的是可以使用背包的lnexp的优化，也可以直接exp。而我们知道平时这两种计算方法是不同的，直接exp只能用于有标号物品的计数，而背包一般用于无标号，式子可以化为polya指数。但在这里，因为我们只关心有用的项，于是非0项最多选一次。这种条件下这两种计算方法就都正确了。

#include<bits/stdc++.h>
using namespace std;
const int N=3e5+50,mod=1e9+7;
int n,a[N],mx,lim,f[20][N],b[N],g[20][N],inv[N],ans,mindiv[N],p[N],tot,phi[N];
int read(){
    int x=0,c;
    while(!isdigit(c=getchar()));
    while(isdigit(c))x=x*10+c-48,c=getchar();
    return x;
}
void FWT(int *a,int op){
    for(int i=1;i<lim;i<<=1)
        for(int j=0;j<lim;j+=i<<1)
            for(int k=0;k<i;k++)
                (a[i+j+k]+=op*a[j+k])%=mod;
}
int main(){
    scanf("%d",&n);
    for(int i=1,x;i<=n;i++)a[x=read()]++,mx=max(mx,x);
    lim=1;n=0;while(lim<=mx)lim<<=1,n++;
    inv[1]=b[1]=phi[1]=1;
    for(int i=2;i<=lim;i++){
        b[i]=b[i>>1]+(i&1);inv[i]=mod-1ll*mod/i*inv[mod%i]%mod;
        if(!mindiv[i])mindiv[i]=p[++tot]=i,phi[i]=i-1;
        for(int j=1,y;j<=tot&&p[j]<=mindiv[i]&&(y=p[j]*i)<=lim;j++)
            mindiv[y]=p[j],phi[y]=phi[i]*(i%p[j]?p[j]-1:p[j]);
    }
    for(int i=1;i<lim;i++)f[b[i]][i]=a[i];
    for(int i=1;i<=n;i++){
        FWT(f[i],1);
        for(int j=0;j<lim;j++)f[i][j]=1ll*f[i][j]*i%mod;
    }
    for(int i=0;i<lim;i++){
        g[0][i]=1;
        for(int j=1;j<=n;j++){
            int dat=0;
            for(int k=1;k<=j;k++)
                dat=(dat+1ll*f[k][i]*g[j-k][i])%mod;
            g[j][i]=1ll*dat*inv[j]%mod;
        }
    }
    for(int i=0;i<=n;i++)FWT(g[i],-1);
    for(int i=0;i<lim;i++)ans=(ans+1ll*g[b[i]][i]*phi[i+1])%mod;
    for(int i=1;i<=a[0];i++)ans=2*ans%mod;
    cout<<(ans+mod)%mod;
    return 0;
}

还有一个比较神奇的题loj6622，它是每一位都不同的FWT，那么就每一位分别按照对应的规则处理即可。有一种比较理性的理解方式是它相当于 $w$ 个不同的集合幂级数套起来，即外层的集合幂计数是以内层集合幂级数为元素的。我们已经见过集合幂级数套形式幂级数，所以这个大概也能理解。

Prutekoi's blog

UOJ310 黎明前的巧克力

子集卷积

集合幂exp

AGC041C（构造神题）