哈集幂

WZH2026-08-102026-08-20

哈集幂

哈集幂是啥？能吃吗？

位运算卷积

对于长度为 $2^n$ 的序列 $a,b$ ，定义 $a$ 和 $b$ 的卷积结果为 $c$ 当且仅当：

$\forall i\in[0,2^n-1],\ c_i=\sum_{j\oplus k}a_jb_k$ 。

对于 $\oplus$ 分别为与运算，或运算和异或运算时，我们可以使用 FWT 求解 $c$ 。

这个东西长得很像 FFT 的加法卷积形式，所以我们也考虑对序列 $a$ 和 $b$ 分别变换为 $A$ 和 $B$ 后点乘，之后再逆变换回来。

然后就是极具注意力的东西了。

或运算卷积

注意到 $j|k=i \ \to \ (j|k)|i=i$ 且 $j|i=i,k|i=i \ \to \ (j|k)|i=i$

所以定义 $A_i=\sum_{j|i=i}a_j$ 。

那么不难发现：

\begin{aligned} A_i\times B_i &=(\sum_{j|i=i}a_j)(\sum_{k|i=i}b_k)\\ &=\sum_{j|i=i,k|i=i}a_jb_k\\ &=\sum_{(j|k)|i=i}a_jb_k\\ &=C_i \end{aligned}

所以变换 $A_i=\sum_{j|i=i}a_j$ 就行。

我们考虑类似 FFT 的分治计算。

不妨设每次变换后的左侧为 $a_0$ ，右侧为 $a_1$ 。

那么容易发现，左侧的 $a_0$ 中的每一个值必定不会受到 $a_1$ 的影响，因为左侧的数当前考虑下的做高位必定为 $0$ ，所以可以直接继承。同理，右边的每一个数一定可以继承左边的数。于是，我们得到如下公式：

a=merge(a_0,a_0+a_1)

其中 $+$ 表示按位加， $merge$ 表示拼接。

逆变换就把上面的东西逆过来就行：

a=merge(a_0,a_1-a_0)

代码：

void FWT(int f[],int t){
    for(int i=2;i<=(1<<n);i<<=1)
        for(int j=0;j<(1<<n);j+=i)
            for(int k=j;k<(j+(i>>1));k++)
                f[k+(i>>1)]+=t*f[k];
}

与运算卷积

与上面类似。

代码：

void FWT(int f[],int t){
    for(int i=2;i<=(1<<n);i<<=1)
        for(int j=0;j<(1<<n);j+=i)
            for(int k=j;k<(j+(i>>1));k++)
                f[k]+=t*f[k+(i>>1)];
}

异或运算卷积

这谁能想到（除了用矩阵理解）。

定义 $A_i=\sum\limits_{popcount(i\& j)=0}a_j-\sum\limits_{popcount(i\& j)=1}a_j$ 。

其中 $popcount(i)$ 表示二进制下 $i$ 的 $1$ 的个数的奇偶性。

然后这个运算规则有一些神秘的性质（我感觉第一个想出来这个的人肯定是用矩阵的那个方法想出来的，这个只是他根据矩阵刻意造出来的东西）。

总之这个是对的。

然后正变换是（显然的吧）：

a=merge(a_0+a_1,a_0-a_1)

逆变换：

a=merge(\frac{a_0+a_1}{2},\frac{a_0-a_1}{2})

代码：

void FWT(int *f,int t){
    for(int i=2;i<=m;i<<=1){
        for(int j=0;j<m;j+=i){
            for(int k=j;k<(j+(i>>1));k++){
                int x=f[k],y=f[k+(i>>1)];
                if(t==0)f[k]=(x+y)%P,f[k+(i>>1)]=(x-y+P)%P;
                else f[k]=(1ll*inv2*(x+y)%P),f[k+(i>>1)]=1ll*inv2*((x-y+P)%P)%P;
            }
        }
    }
}

子集卷积

上面那些东西~~统统没用~~。

重要的是这个子集卷积以及后面的哈集幂。

子集卷积：定义长度为 $2^n$ 的序列 $a$ 和 $b$ ，定义他们的子集卷积为 $c$ 当且仅当：

\forall i\in[0,2^n-1],\ c_i=\sum_{\substack{{j|k=i} \\ {j\& k=0}}}a_jb_k

很明显这个的求解方法跟或运算卷积有关。

但是直接 FWT 会出问题，因为没有考虑到 $j\& k=0$ 的限制。

不妨思考 $j\& k=0$ 意味着什么。

可以发现 $j\& k=0\ \Leftrightarrow\ popcount(j)+popcount(k)=popcount(j|k)$ ，其中 $popcount(i)$ 表示 $i$ 二进制下 $1$ 的个数。

也就是说，如果我扩展一维 FWT ，那么这个问题就变得可做了。

具体的，定义 $A_{i,j}=\begin{cases}0 & popcount(j)\ne i\\ a_j & popcount(j)=i\end{cases}$ ，然后我们对于 $A$ 的每一位 $A_{i}$ 和 $B$ 的每一位 $B_{i}$ 都进行一边 FWT 。

然后，我们不能直接点乘。所以我们可以这么做：对于每一个 $k$ ，执行 $C_{i,k}=\sum_j A_{j,k}B_{i-j,k}$ 。

最后在对 $C$ 的每一位 $C_i$ 作 IFWT 就行。

代码：

#include <bits/stdc++.h>
using namespace std;
const int N=2000010,P=1000000009;
int n,a[21][N],b[21][N],c[21][N];
#define ct(i) (__builtin_popcount(i))
void FWT(int *a,int t){
    for(int i=2;i<=(1<<n);i<<=1)
        for(int j=0;j<(1<<n);j+=i)
            for(int k=j;k<j+(i>>1);k++)
                (a[k+(i>>1)]+=(P+a[k]*t)%P)%=P;
}
signed main(){
    cin>>n;
    for(int i=0,x;i<(1<<n);i++)cin>>x,a[ct(i)][i]=x;
    for(int i=0,x;i<(1<<n);i++)cin>>x,b[ct(i)][i]=x;
    for(int i=0;i<=n;i++)FWT(a[i],1),FWT(b[i],1);
    for(int i=0;i<=n;i++)
        for(int j=0;j<=i;j++)
            for(int k=0;k<(1<<n);k++)  
                c[i][k]+=1ll*a[j][k]*b[i-j][k]%P,c[i][k]%=P;
    for(int i=0;i<=n;i++)FWT(c[i],-1);
    for(int i=0;i<(1<<n);i++)cout<<c[ct(i)][i]<<" ";
    return 0;
}

复杂度 $O(n^22^n)$ 。

哈集幂

这是一个类（ chao ）似（ xi ）形式幂级数的玩意。

全称就是大名鼎鼎的——集合幂级数。

定义一个长度为 $2^n$ 的序列 $a$ 对应的集合幂级数 $A$ 为：

\sum_S a_Sx^S

注意这里的 $x$ 只是一个占位符，跟生成函数的一样，只是证明这个是第 $S$ 项。

同时 $S$ 是一个集合，可以进行所有集合的运算，一般的可以用二进制数代替。

对于哈集幂 $A,B$ ， $A\times B$ 一般有以下几种：

并卷积。
交卷积。
对称差卷积。
子集卷积。

很显然只有最后一个有用（不然最后一个还有什么用）。

考虑刚才定义的子集卷积在集合幂级数意义下是个什么东西：

首先看条件： $j|k=i$ 且 $j\& k=0$ 。

容易发现这个意义是把 $i$ 划分成两个无交的集合后的卷积。

现在我们把子集卷积写成哈集幂的语言：

c_S=\sum_{T\subseteq S}a_Tb_{S/T}

这个还是挺有用的。

因为 FWT 是线性变换！也就是说，类似矩阵的 $min-plus$ 扩展， FWT 也可以求解 $\max_{j|i=i}f_j$ 之类的东西。

那么这个注定了子集卷积和状压 DP 十分般配。

例如这个题：[USACO22FEB] Redistributing Gifts G 。

这是一个状压 DP 的题目，可以使用 $O(3^n)$ 的算法通过。

但是某些题解里说 $O(3^n)$ 大概率是信息极限，只是这个题的特殊之处可以让他优化为 $O(n^22^n)$ 。

但是其实不是这样，因为可以使用哈集幂全家桶轻轻松松优化，无需动脑。

接下来就是一些科技性的东西。

半在线集合幂级数子集卷积

其实如果联想到分治 FFT 的半在线卷积的话，可能会认为半在线子集卷积乃至集合幂级数求逆都会崩坏到 $O(n^32^n)$ ，但实际上不是。

因为子集卷积多加了一维，同时半在线子集卷积的情况下，一个集合 $S$ 能受到的所有转移的集合 $T$ 必然满足 $|T|\le |S|$ 。所以这启发我们可以按照第一位集合大小的顺序转移。

可以看一下代码理解：

for(int i=1;i<=n;i++){
    for(int j=0;j<i;j++)
        for(int k=0;k<(1<<n);k++)
            (g[i][k]+=1ll*g[j][k]*f[i-j][k]%P)%=P;
}

复杂度 $O(n^22^n)$ 。

集合幂级数子集卷积求逆

好吧，这个其实就跟分治 FFT 可以做多项式求逆一样，这个需要用半在线子集卷积做。

十分的模板。

代码：

#include <bits/stdc++.h>
using namespace std;
const int N=20,P=998244353;
int a[1<<N],n,f[N][1<<N],g[N][1<<N];
int kpow(int a,int b){
    int t=1;
    for(;b;b>>=1,a=1ll*a*a%P)
        if(b&1)t=1ll*t*a%P;
    return t;
}
int bt(int i){return __builtin_popcount(i);}
void FWT(int f[]){
    for(int i=2;i<=(1<<n);i<<=1)
        for(int j=0;j<(1<<n);j+=i)
            for(int k=j;k<(j+(i>>1));k++)
                (f[k+(i>>1)]+=f[k])%=P;
}
void IFWT(int f[]){
    for(int i=2;i<=(1<<n);i<<=1)
        for(int j=0;j<(1<<n);j+=i)
            for(int k=j;k<(j+(i>>1));k++)
                (f[k+(i>>1)]+=P-f[k])%=P;
}
int main(){
    scanf("%d",&n);
    for(int i=0;i<(1<<n);i++)scanf("%d",&a[i]);
    for(int i=0;i<(1<<n);i++)f[bt(i)][i]=a[i];
    int z=kpow(a[0],P-2);
    g[0][0]=z;
    for(int i=0;i<=n;i++)FWT(f[i]);
    FWT(g[0]);
    for(int i=1;i<=n;i++){
        for(int j=0;j<i;j++)
            for(int k=0;k<(1<<n);k++)
                (g[i][k]+=1ll*g[j][k]*f[i-j][k]%P)%=P;
        for(int j=0;j<(1<<n);j++)g[i][j]=1ll*g[i][j]*(P-z)%P;
    }
    for(int i=0;i<=n;i++)IFWT(g[i]);
    for(int i=0;i<(1<<n);i++)printf("%d ",g[bt(i)][i]);
    return 0;
}

这个可能是最没用的了，因为我不知道他的组合意义是啥。

集合幂级数子集卷积 exp

组合意义天崩地裂。

这个和求逆有着鲜明的对比，因为 $e^F$ 这样子的东西一般有巨大的组合意义。

联系一下子集卷积的组合意义，容易发现 $[x^S]e^F$ 的组合意义实际上是：

将 $S$ 划分为若干个无交的子集后（不区分顺序）的权值的和。

一种划分的权值定义为这个划分涉及的所有子集的权值的乘积。

一般的这个和 ln 有两种求法：一个是基于半在线子集卷积的，和形式幂级数有点像的方法，适用面较小；另一种是基于组合意义的，适用面广大。

这里记录的是组合意义的。

考虑钦定集合中最大的数为 $i$ ，那么就有：

g_{S\cup \{i\}}=\sum_{T\subseteq S}g_Tf_{S/T\cup \{i\}}

然后我们可以按照最大元 $i$ 的顺序转移。每次将上一轮的结果 $g$ 和这一轮将要被变换的 $f$ FWT 变换后执行子集卷积就行。

代码：

#include <bits/stdc++.h>
using namespace std;
const int N=20,P=998244353;
int a[1<<N],n,f[N][1<<N],g[N][1<<N];
int kpow(int a,int b){
    int t=1;
    for(;b;b>>=1,a=1ll*a*a%P)
        if(b&1)t=1ll*t*a%P;
    return t;
}
int bt(int i){return __builtin_popcount(i);}
void FWT(int f[],int n){
    for(int i=2;i<=(1<<n);i<<=1)
        for(int j=0;j<(1<<n);j+=i)
            for(int k=j;k<(j+(i>>1));k++)
                (f[k+(i>>1)]+=f[k])%=P;
}
void IFWT(int f[],int n){
    for(int i=2;i<=(1<<n);i<<=1)
        for(int j=0;j<(1<<n);j+=i)
            for(int k=j;k<(j+(i>>1));k++)
                (f[k+(i>>1)]+=P-f[k])%=P;
}
int main(){
    scanf("%d",&n);
    for(int i=0;i<(1<<n);i++)scanf("%d",&a[i]);
    for(int i=0;i<(1<<n);i++)f[bt(i)][i]=a[i];
    g[0][0]=1;
    for(int i=1;i<=n;i++){
        int u=(1<<i-1);
        for(int j=1;j<=i;j++)FWT(f[j]+u,i-1);
        for(int j=0;j<i;j++)FWT(g[j],i-1);
        for(int j=0;j<i;j++)
            for(int k=1;j+k<=i;k++)
                for(int p=0;p<(1<<i-1);p++)
                    (g[j+k][p|u]+=1ll*g[j][p]*f[k][p|u]%P)%=P;
        for(int j=1;j<=i;j++)IFWT(g[j]+u,i-1);
        for(int j=0;j<i;j++)IFWT(g[j],i-1);
    }
    for(int i=0;i<(1<<n);i++)printf("%d ",g[bt(i)][i]);
    return 0;
}

集合幂级数子集卷积 ln

考虑对上面 exp 的式子变形：

g_{S\cup \{i\}}=\sum_{T\subseteq S}g_Tf_{S/T\cup \{i\}}

f_{S\cup\{i\}}=g_{S\cup \{i\}}-\sum_{T\subseteq S,T\ne \varnothing}g_Tf_{S/T\cup \{i\}}

类似的，可以钦定最大元，按照最大元的顺序转移。这样每次需要执行半在线子集卷积。

#include <bits/stdc++.h>
using namespace std;
const int N=20,P=998244353;
int a[1<<N],n,f[N][1<<N],g[N][1<<N];
int bt(int i){return __builtin_popcount(i);}
void FWT(int f[],int n){
    for(int i=2;i<=(1<<n);i<<=1)
        for(int j=0;j<(1<<n);j+=i)
            for(int k=j;k<(j+(i>>1));k++)
                (f[k+(i>>1)]+=f[k])%=P;
}
void IFWT(int f[],int n){
    for(int i=2;i<=(1<<n);i<<=1)
        for(int j=0;j<(1<<n);j+=i)
            for(int k=j;k<(j+(i>>1));k++)
                (f[k+(i>>1)]+=P-f[k])%=P;
}
int main(){
    scanf("%d",&n);
    for(int i=0;i<(1<<n);i++)scanf("%d",&a[i]);
    for(int i=0;i<(1<<n);i++)f[bt(i)][i]=a[i];
    g[0][0]=0;
    for(int i=1;i<=n;i++){
        int u=(1<<i-1);
        for(int j=0;j<i;j++)FWT(f[j],i-1);
        g[1][u]=f[1][u];
        FWT(g[1]+u,i-1);
        for(int j=2;j<=i;j++){
            for(int k=1;k<j;k++)
                for(int p=0;p<u;p++)
                    (g[j][p|u]+=1ll*g[k][p|u]*f[j-k][p]%P)%=P;
            IFWT(g[j]+u,i-1);
            for(int k=0;k<u;k++)g[j][k|u]=(f[j][k|u]+P-g[j][k|u])%P;
            FWT(g[j]+u,i-1);
        }
        for(int j=0;j<i;j++)IFWT(f[j],i-1);
        for(int j=1;j<=i;j++)IFWT(g[j]+u,i-1);
    }
    for(int i=0;i<(1<<n);i++)printf("%d ",g[bt(i)][i]);
    return 0;
}