快速沃尔什变换

Published: April 24, 2019 by Daltao

• Categories:
• algorithm 101

• Tags:

• 引言
• 或运算
• 且运算
• 异或运算
• 快速子集卷积
• K进制FWT
  • 最大值运算
  • 最小值运算
  • 不进位加法
    • 不进位加法子集统计
• 位独立运算
• 子集和计数
• 参考资料

引言

快速沃尔什变换（Fast Walsh Transform）适用于计算一类多项式卷积的高效算法。定义

$$C=A\otimes B=\sum_{k=0}^nX^k\sum_{i\oplus j=k}A_iB_j$$

其中$A$，$B$，$C$均为$n$阶多项式。而$A_i$,$B_j$分别表示多项式$A$中$X^i$项的系数和多项式$B$中$X^j$项的系数。

看着眼熟吧，这不是和多项式的乘法非常像吗，当$i\oplus j=i+j$时，上面就是我们熟知的多项式乘法公式。我们知道解决多项式乘法不仅有$O(n^2)$的朴素算法，还有$O(n\log_2n)$的快速傅里叶变换。快速傅里叶变换实际上是将两个多项式$A$,$B$转换为点值表示法DFT(A)和DFT(B)，之后利用向量乘法得到DFT(C)=DFT(A)DFT(B)，最后从DFT(C)中还原多项式$C$。我们不免想到，是否能利用同样的技术进行加速呢？

或运算

如果$i\oplus j=i\mid j$，那么我们可以定义：

$$FWT(A)=\sum_{i=0}^{n}X^i\sum_{j\in i}A_j$$

其中$j\in i$表示j中$1$出现的二进制位置是$i$的子集，换言之$i=i\mid j$。我们注意到

$$\begin{aligned} FWT(C)_k&=\sum_{t\in k}C_t\\ &=\sum_{t\in k}\sum_{i\mid j=t}A_iB_j\\ &=\sum_{i\mid j\in k}A_iB_j\\ &=\sum_{i\in k}A_i\sum_{j\in k}B_j\\ &=(\sum_{i\in k}A_i)(\sum_{i\in k}B_i)\\ &=FWT(A)_k\cdot FWT(B)_k \end{aligned}$$

因此我们发现了$FWT(C)=FWT(A)\cdot FWT(B)$。下面我们讨论如何快速计算$FWT(A)$。记$m=\lceil \frac{n}{2} \rceil$，$L(A)=\sum_{i=0}^{m-1}A_iX^i$，$R(A)=\sum_{i=m}^nA_iX^i$。很显然$A=L(A)+R(A)\cdot X^m$。

$$\begin{aligned} FWT(A)&=\sum_{i=0}^{n}X^i\sum_{j\in i}A_j\\ &=\sum_{i=0}^{n}X^i(\sum_{j\in i,j<m}A_j+\sum_{j\in i,j\geq m}A_j)\\ &=\sum_{i=0}^{m-1}X^i(\sum_{j\in i,j<m}A_j+\sum_{j\in i,j\geq m}A_j)+\sum_{i=m}^{n}X^i(\sum_{j\in i,j<m}A_j+\sum_{j\in i,j\geq m}A_j)\\ &=\sum_{i=0}^{m-1}X^i\sum_{j\in i}L(A)_j+X^m\sum_{i=0}^{m-1}X^i(\sum_{j\in i}L(A)_j+\sum_{j+m\in i+m}R(A)_j)\\ &=FWT(L(A))+X^m(FWT(L(A))+FWT(R(A))) \end{aligned}$$

我们可以简单地记作

$$FWT(A)=(FWT(L(A)), FWT(L(A))+FWT(R(A)))$$

这样我们可以每次都将$A$拆分为前部和后部进行分治计算。时间复杂度为$O(n\log_2n)$。而$FWT$的逆也很容易得到：

$$\begin{aligned} FWT^{-1}(A)&=FWT^{-1}(L(A))+X^mFWT^{-1}(R(A)-L(A))\\ &=(FWT^{-1}(L(A)),FWT^{-1}(R(A)-L(A))) \end{aligned}$$

同样可以采用分治算法解决。

且运算

如果$\oplus$代表且运算，那么$FWT$函数定义如下：

$$FWT(A)=\sum_{i=0}^nX^i\sum_{i\in j}A_j$$

其余推理类似，不再赘述，直接给出公式：

$$\begin{aligned} &FWT(C)=FWT(A)\cdot FWT(B)\\ &FWT(A)=(FWT(L(A))+FWT(R(A)),FWT(R(A)))\\ &FWT^{-1}(A)=(FWT^{-1}(L(A)-R(A)),FWT^{-1}(R(A))) \end{aligned}$$

异或运算

如果$\oplus$代表亦或运算。记$E$为所有二进制形式中1的个数为偶数个的正整数集合，而$O$表示所有二进制形式中1的个数为奇数个的正整数集合。那么$FWT$函数定义如下：

$$FWT(A)=\sum_{i=0}^nX^i(\sum_{i\&j\in E}A_j-\sum_{i\&j\in O}A_j)$$

由于（可以通过枚举证明）

$$(i\&j)\oplus k=(i\oplus k)\&(j\oplus k)$$

因此：

$$\begin{aligned} FWT(C)_k&=\sum_{k\&t\in E}C_t-\sum_{k\&t\in O}C_t\\ &=\sum_{k\&t\in E}\sum_{i\oplus j=t}A_iB_j-\sum_{k\&t\in O}\sum_{i\oplus j=t}A_iB_j\\ &=\sum_{k\&(i\oplus j)\in E}A_iB_j-\sum_{k\&(i\oplus j)\in O}A_iB_j\\ &=\sum_{(k\&i)\oplus (k\& j)\in E}A_iB_j-\sum_{(k\&i)\oplus (k\& j)\in O}A_iB_j\\ \end{aligned}$$

记$b(i)$表示$i$的二进制形式中$1$的个数。记$r$表示$i\oplus j$中可能的$1$的数量，初始值为$b(i)+b(j)$。遍历每一位，若浏览某一位时，$i$与$j$均为$0$，则$r$不变，若一者为$1$，$r$依旧不变，否则二者都为$1$，则$r$减少2。很显然这个算法最终得到的就是$b(i\&j)$。因此我们证明了$b(i\&j)$与$b(i)+b(j)$的二进制形式中1出现的次数拥有相同的奇偶性。

$$\begin{aligned} &=\sum_{k\&i \in E}A_i\sum_{k\&j\in E}B_j+\sum_{k\&i \in O}A_i\sum_{k\&j\in O}B_j-\sum_{k\&i \in E}A_i\sum_{k\&j\in O}B_j-\sum_{k\&i \in O}A_i\sum_{k\&j\in E}B_j\\ &=(\sum_{k\&i \in E}A_i-\sum_{k\&i \in O}A_i)(\sum_{k\&i \in E}B_i-\sum_{k\&i \in O}B_i）\\ &=FWT(A)_kFWT(B)_k \end{aligned}$$

因此我们可以推出：

$$FWT(C)=FWT(A)\cdot FWT(B)$$

接着我们考虑如何拆分多项式。

$$\begin{aligned} FWT(A)&=\sum_{i=0}^nX^i(\sum_{i\&j\in E}A_j-\sum_{i\&j\in O}A_j)\\ &=\sum_{i=0}^nX^i(\sum_{i\&j\in E,j<m}A_j+\sum_{i\&j\in E,j\geq m}A_j-\sum_{i\&j\in O,j<m}A_j-\sum_{i\&j\in O,j\geq m}A_j)\\ &=\sum_{i=0}^{m-1}X^i(\sum_{i\&j\in E,j<m}A_j+\sum_{i\&j\in E,j\geq m}A_j-\sum_{i\&j\in O,j<m}A_j-\sum_{i\&j\in O,j\geq m}A_j)\\ &+\sum_{i=m}^nX^i(\sum_{i\&j\in E,j<m}A_j+\sum_{i\&j\in E,j\geq m}A_j-\sum_{i\&j\in O,j<m}A_j-\sum_{i\&j\in O,j\geq m}A_j)\\ &=\sum_{i=0}^{m-1}X^i(\sum_{i\&j\in E}L(A)_j+\sum_{i\&j\in E}R(A)_j-\sum_{i\&j\in O}L(A)_j-\sum_{i\&j\in O}R(A)_j)\\ &+X^m\sum_{i=0}^{m-1}X^i(\sum_{i\&j\in E}L(A)_j+\sum_{i\&j\in O}R(A)_j-\sum_{i\&j\in O}L(A)_j-\sum_{i\&j\in E}R(A)_j)\\ &=FWT(L(A))+FWT(R(A))+X^m(FWT(L(A))-FWT(R(A)))\\ &=(FWT(L(A))+FWT(R(A)),FWT(L(A))-FWT(R(A))) \end{aligned}$$

而逆函数容易得到：

$$FWT^{-1}(A)=(FWT^{-1}(\frac{L(A)+R(A)}{2}),FWT^{-1}(\frac{L(A)-R(A)}{2}))$$

整体的时间复杂度为$O(n\log_2n)$。

题目1：给定长度为$2^m$的向量$x$，要求计算$n$个连续的$x$的异或卷积：$x\oplus x\oplus \ldots \oplus x$。其中$1\leq m\leq 20$，$n\leq 10^{18}$，结果对素数$p$取模。

考虑到$FWT(x^n)=FWT(x)^n$，因此可以先对$x$求一次FWT，之后将每个元素$x_i$替换为$x_i^n$，最后IFWT恢复。

题目2：给定长度为$2^m$的向量$x$，要求计算$n$个连续的$x$的异或卷积：$x\oplus x\oplus \ldots \oplus x$。其中$1\leq m\leq 20$，$n\leq 10^{18}$，结果对任意数$p$取模，其中$1\leq p\leq 10^9$。

由于IFWT的时候需要做除2操作，因此这里不能直接使用。有一种叫做K进制FWT的技术，其只需要在做IFWT的最后阶段，将整个向量除上$2^m$即可。但是这里依旧不能保证$gcd(2^m,p)=1$，因此我们需要将$p$先乘上$2^m$做取模，之后每个向量元素能整除$2^m$的性质就不会被影响。最后的阶段才将整个向量对$p$取模。

题目3：给定两个序列$A_0,b$，其中$A_0$的长度为$2^m$，$b$的长度为$m+1$。定义$A_{i,j}=\sum_{k}A_{i-1,k}b[bitcount(k\oplus j)]$。要求输出$A_n$，结果对$p$取模。其中$1\leq m\leq 20$，$1\leq n\leq 10^{18}$

提供一道题目。

我们将$b$展开，定义$c[i]=b[bitcount(i)]$，那么我们要求的就是$A_{i,j}=\sum_{k}A_{i-1,k}c[k\oplus j]$。可以发现$A_i=A_{i-1}\oplus c$，因此结果为$A_n=A_{0}\oplus c^n$。

我们可以用题目$2$提到的方法计算出最终结果。

快速子集卷积

考虑这样一个问题，给定序列$a$和$b$，要求找到另外一个序列$c$，满足：

$$c_i=\sum_{j\mid k=i\land j\&k=0}a_jb_k$$

我们可以定义$A_{i,j}=a_j[bitcount(j)=i]$，同理定义$B$和$C$。那么考虑$T_k=\sum_{i=0}^kA_{i}\oplus B_{k-i}$，其与$C_k$的区别非常小，实际上$C_{k,i}=T_{k,i}[bitcount(i)=k]$。

因此如果我们完成上面共$n^2$次卷积，就可以求出$C_1,C_2,\ldots$，而我们要求的结果为$c=\sum_iC_i$。

上面的过程时间复杂度为$O(n^32^n)$。

我们考虑到可以预先处理出$A_1,A_2,\ldots$以及$B_1,B_2,\ldots$的FWT形式，然后两两点积即可，最后再整体做一次IFWT即可（FWT和IFWT都是线性变换）。即$T_{k}=IFWT(\sum_{i=0}^kFWT(A_{i})\oplus FWT(B_{k-i}))$。这样就只需要做$n^2$次的点积以及$O(n)$次的FWT和IFWT操作即可，时间复杂度为$O(n^22^n)$。

K进制FWT

本章主要参考位运算卷积(FWT) & 集合幂级数。

考虑$A,B$是两个定义在$\mathbb{Z}_k^{k^n}$上的两个向量。记$C=A*B$，定义$C_i=\sum_{j\oplus k=i}A_jB_k$。

考虑我们现在要找到一个可逆矩阵$F$，满足$F(A)\cdot F(B)=F(A* B)$，这里的$\cdot$是点积的意思。这样我们就可以通过$F^{-1}(F(A)* F(B))$快速得到$A* B$。

简单令$c(i,j)=F_{i,j}$。可以推出：

$$\begin{aligned} \sum_{j=0}^{k^n-1}c(i,j)A_j\sum_{t=0}^{k^n-1}c(i,t)B_t&=\sum_{j=0}^{k^n-1}c(i,j)C_j\\ \Rightarrow \sum_{j=0}^{k^n-1}\sum_{t=0}^{k^n-1}c(i,j)c(i,t)A_jB_t&=\sum_{j=0}^{k^n-1}c(i,j)\sum_{t\oplus l=j}A_tB_l\\ \Rightarrow \sum_{j=0}^{k^n-1}\sum_{t=0}^{k^n-1}c(i,j)c(i,t)A_jB_t&=\sum_{j=0}^{k^n-1}\sum_{t=0}^{k^n-1}c(i,j\oplus t)A_jB_t \end{aligned}$$

可以得出$c(i,j)c(i,t)=c(i,j\oplus t)$。

考虑到位运算可以逐位处理，简单记$x^{(i)}$表示$k$进制下$x$的第$i$位的值。因此我们可以简单的令$c(i,j)=\prod_t c(i^{(t)},j^{(t)})$。这样我们就只需要考虑$k\times k$的一个矩阵。

接下来考虑在给定$c$的前提下快速计算FWT的算法。很显然直接用矩阵乘法的时间复杂度为$O(k^{2n})$，下面给个更快的分治法算法。

$$\begin{aligned} F(A)_i&=\sum_{j=0}^{k^n-1} c(i,j)A_j\\ &=\sum_{b=0}^{k-1} \sum_{j=bk^{n-1}}^{(b+1)k^{n-1}-1}c(i,j)A_j \end{aligned}$$

这里简单记$i'$表示$i$去掉k进制最高位后的值，$A[i]$。表示将$A$均分为$k$段，第$i$段对应的向量。

$$\begin{aligned} &=\sum_{b=0}^{k-1} \sum_{j=bk^{n-1}}^{(b+1)k^{n-1}-1}c(i^{(n-1)},j^{(n-1)})c(i',j')A_j\\ &=\sum_{b=0}^{k-1} c(i^{(n-1)},b)\sum_{j=bk^{n-1}}^{(b+1)k^{n-1}-1}c(i',j')A_j\\ &=\sum_{b=0}^{k-1} c(i^{(n-1)},b)F(A[b])_{i'}\\ \end{aligned}$$

上面给出的算法的时间复杂度为$O(nk^{n+1})$。而IFWT则类似，只是替换了$c$数组，并且先做还原操作，后递归分治。

最大值运算

按位取最大值操作在$k=2$时对应的就是或运算。

考虑到$c(x,y)c(x,y)=c(x,\max(y,y))$，可以推出$c(x,y)$只可能为$0$或$1$。

对于任意$l<r$，有$c(x,l)c(x,r)=c(x,r)$。这意味着$c(x,l)=1$或$c(x,r)=0$，无论哪种情况都有$c(x,l)\geq c(x,r)$。故可以发现$c(x,?)$是个前缀为$1$，后缀为$0$的向量。在满足条件的矩阵中有多个选择，我们选择任意一个可逆的矩阵即可，比如下面矩阵。

$$\left[ \begin{array}{ccccc} 1 & 0 & 0 & \cdots & 0\\ 1 & 1 & 0 & \cdots & 0\\ 1 & 1 & 1 & \cdots & 0\\ \cdots & \cdots & \cdots & \dots & \cdots\\ 1 & 1 & 1 & \cdots & 1 \end{array} \right]$$

它的逆矩阵为：

$$\left[ \begin{array}{ccccc} 1 & 0 & 0 & \cdots & 0\\ -1 & 1 & 0 & \cdots & 0\\ 0 & -1 & 1 & \cdots & 0\\ \cdots & \cdots & \cdots & \dots & \cdots\\ 0 & 0 & 0 & \cdots & 1 \end{array} \right]$$

一般做法时间复杂度为$O(nk^{n+1})$，但是由于两个矩阵分别是前缀和和差分矩阵，因此可以$O(nk^n)$计算。

最小值运算

按位取最小值操作在$k=2$时对应的就是且运算。

考虑到$c(x,y)c(x,y)=c(x,\min(y,y))$，可以推出$c(x,y)$只可能为$0$或$1$。

对于任意$l<r$，有$c(x,l)c(x,r)=c(x,l)$。这意味着$c(x,l)=0$或$c(x,r)=1$，无论哪种情况都有$c(x,l)\leq c(x,r)$。故可以发现$c(x,?)$是个前缀为$0$，后缀为$1$的向量。在满足条件的矩阵中有多个选择，我们选择任意一个可逆的矩阵即可，比如下面矩阵。

$$\left[ \begin{array}{ccccc} 1 & \cdots & 1 & 1 & 1\\ \cdots & \cdots & \cdots & \dots & \cdots\\ 0 & \cdots &1 & 1 & 1\\ 0 & \cdots &0 & 1 & 1\\ 0 & \cdots &0 & 0 & 1 \end{array} \right]$$

它的逆矩阵为：

$$\left[ \begin{array}{ccccc} 1 & \cdots & 0 & 0 & 0\\ \cdots & \cdots & \cdots & \dots & \cdots\\ 0 & \cdots &1 & -1 & 0\\ 0 & \cdots &0 & 1 & -1\\ 0 & \cdots &0 & 0 & 1 \end{array} \right]$$

一般做法时间复杂度为$O(nk^{n+1})$，但是由于两个矩阵分别是后缀和和差分矩阵，因此可以$O(nk^n)$计算。

不进位加法

不进位加法在$k=2$的时候对应的就是异或运算。考虑到$c(x,l)c(x,r)=c(x,l\oplus r)$，因此可以认为这个矩阵的每一行都有循环的性质。如果我们取一个$k$次单位本原根$w_k$。并且令矩阵$F_{i,j}=w_k^{i\times j}$，那么线性变换$F$实际上是范德蒙德矩阵，其逆矩阵满足$F^{-1}_{i,j}=\frac{1}{k}w_k^{-i\times j}$。

如果我们成功找到了$k$次单位本原根，那么时间复杂度为$O(nk^{n+1})$。

当然我们并不能一定找到这样一个$k$次单位本原根。找不到怎么办。我们可以类似复数加入$i$一样，我们加入一个值$x$扩充我们的代数结构，且满足$x^1,\ldots,x^{n-1}\neq 1$且$x^n=1$。于是我们现在需要通过一个$k-1$阶多项式来表示我们的代数中的任意值。

一般到这里我们为了避免多项式变得过大，可以让其对$x^k-1$取模。但是对$x^k-1$取模的情况下，我们的代数结构并不是一个整环，这样就不能保证$FF^{-1}=I$的成立。一个简单的解决方案就是我们在计算的时候对分圆多项式$\Phi_k(x)$取模，这时候可以保证所有多项式都可逆。

上面的过程已经给我们提供了$O(nk^{n+3})$时间复杂度的算法。这里由于$\Phi_k(x)| x^n-1$，因此我们在计算的过程中可以让中间结果对$x^n-1$，而最后要取得最终结果的时候才对$\Phi_k(x)$取模，这样可以大幅加快取模的效率。时间复杂度可以优化到$O(nk^{n+2})$。

提供几道题目：

• Radix sum
• Games

不进位加法子集统计

考虑有$m$个$\mathbb{Z}_k^n$的向量组成的向量组$v_1,\ldots,v_m$，对于所有$u\in \mathbb{Z}_k^n$，输出有多少$V$的子集，其子集和正好为$u$。答案对素数$p$取模。其中$1\leq k\leq 6$，$1\leq n\leq 6$，$1\leq m\leq 10^6$。

这种问题还是比较常见的，提供几道题目：

• 算力训练

做法很神奇。

首先我们记$A_i$表示长度为$k^n$的一个计数数组，其中仅$v_i$和$0$被设置为$1$，其它全为$0$。而我们要求的实际上是$P=\prod_{i=1}^nA_i$。

由于不好直接算，所以我们需要惯例先算出$F(A_i)$，之后通过$F(P)=\prod_{i=1}^nF(A_i)$来得到中间结果，最后$P=F^{-1}(F(P))$恢复数据。直接进行这个流程给出一个时间复杂度为$O(mnk^{n+2})$的算法。

下面我们来优化时间复杂度。首先可以发现$F(A_t)_i=1+c(i,v_t)=1+w_k^{\sum_{b=0}^{k-1}i^{(b)}\times v_t^{(b)}}$。因此我们不需要真的做FWT操作，直接通过这个公式就可以得到$F(A_1),\ldots,F(A_m)$，时间复杂度可以优化到$O(mk^n+nk^{n+2})$。如果$v_i=v_j$，那么我们只需要算一次$F(v_i)$和$F(v_j)$，因此$m$也可以去掉，得到时间复杂度$O(k^{2n}+nk^{n+2})$。

实际上我们可以进一步优化。考虑$F(P)_i$仅可能出现$w_k^0,w_k^1,\ldots,w_k^{k-1}$这些项，因此有$F(P)_i=\prod_{j=0}^{k}(1+w_k^j)^{x_{i,j}}$。因此我们只需要算出所有$x_{i,j}$即可通过快速幂得到$F(P)$。一般的时间复杂度为$O(k^{n+3}\log_2 m)$，如果我们预先计算幂处理结果的话，时间复杂度可以优化到$O(\sqrt{m}k^3+k^{n+3})$。

接下来考虑如何快速得到所有的$x_{i,j}$。记$C_i=\sum_{j=1}^m[v_j=i]$，即统计$i$在输入中出现的次数。可以发现$v_j$对于$F(C)_i$的贡献为$c(i,v_j)$，而$x_{i,j}$对$F(C)_i$的贡献为$w_k^j$，因此有：

$$F(C)_i=\sum_{j=0}^{k-1}x_{i,j}w_k^j$$

这是正常情况下的FWT的结果，接下来我们将C矩阵的每个元素取原来的$0\leq z<k$次方，则可以得到$k$组行列式：

$$F_z(C)_i=\sum_{j=0}^{k-1}x_{i,j}w_k^{zj}$$

接下来将$F_0,\ldots,F_{k-1}$作为列组成一个新的矩阵$F'$，将$x$视作一个$k^n\times k$的矩阵，而$c$则是一个范德蒙德矩阵。上面的方程组实际上是：

$$\begin{aligned} F'&=x\times c\\ \Rightarrow F' \times c^{-1}&=x \end{aligned}$$

我们可以先通过$k$次对$C$做FWT算出$F'$，之后右乘范德蒙德矩阵的逆，就可以得出$x$了。这一步总的时间复杂度为$O(nk^{n+3})$。

因此总的时间复杂度为$O(nk^{n+3}+\sqrt{m}k^3)$。特殊的如果$\mathbb{Z}_p$中我们能找到$k$次本原单位根，那么可以将时间复杂度优化到$(nk^{n+2}+\sqrt{m}k)$，即减少一个$k$因子。

位独立运算

考虑这样一个问题，定义一个新的运算$\oplus=(\oplus_0,\oplus_1,\ldots,\oplus_{n-1})$，对于两个$\mathbb{Z}_k$上的向量$a$和$b$，定义它们运算的结果为$a\oplus b=(a_0\oplus_0 b_0,b_1\oplus_1 b_1,\ldots,a_{n-1}\oplus_{n-1} b_{n-1})$。其中$\oplus_i$可以替代为最大、最小、不进位运算。

现在给定两个$\mathbb{Z}_k^{k^n}$上的向量$A,B$，要求计算$C$，其中$C_i=\sum_{j\oplus t=i}A_jB_t$。

其实根据K进制FWT一节的推导可以发现，我们可以让$c(i,j)=\prod_t c_t(i^{(t)},j^{(t)})$，其中$c_t(i,j)c_t(i,p)=c_i(i,j\oplus_t p)$。而分治算法流程是不需要改变的，我们只需要复用其中推导出来的矩阵来进行运算。

因此我们依旧可以$O(nk^{n+2})$来解决这个问题。如果只涉及且和或运算，那么我们可以$O(nk^n)$来解决这个问题。

提供一些题目：

• Belarusian State University

子集和计数

题目1：给定一个序列$a_1,\ldots,a_n$。其中$0\leq a_i< 2^{K}$。要求输出$b_0,\ldots,b_{2^K-1}$，其中$b_i$表示$a$存在多少非空子序列，满足它们的或运算之和正好为$i$。其中$1\leq n\leq 10^6$，$K=20$。

首先我们计算$A_i$，其中$A_i$表示序列中$i$的子集数。这可以通过高维前缀和或者FWT来实现。

之后我们定义$B_i$，其中$B_i$表示有多少非空子序列，其并集是$i$的子集，很显然$B_i=2^{A_i}-1$。

之后我们可以通过高维差分或者FWT从$B$中计算出$b$，时间复杂度为$O(n+K2^K)$。

题目2：给定一个序列$a_1,\ldots,a_n$。其中$0\leq a_i< 2^{K}$。要求输出$b_0,\ldots,b_{2^K-1}$，其中$b_i$表示$a$存在多少非空子序列，满足它们的且运算之和正好为$i$。其中$1\leq n\leq 10^6$，$K=20$。

首先我们计算$A_i$，其中$A_i$表示序列中$i$的超集数。这可以通过高维后缀和或者FWT来实现。

之后我们定义$B_i$，其中$B_i$表示有多少非空子序列，其交集是$i$的超集，很显然$B_i=2^{A_i}-1$。

之后我们可以通过高维差分或者FWT从$B$中计算出$b$，时间复杂度为$O(n+K2^K)$。

题目3：给定一个序列$a_1,\ldots,a_n$。其中$0\leq a_i< 2^{K}$。要求输出$b_0,\ldots,b_{2^K-1}$，其中$b_i$表示$a$存在多少非空子序列，满足它们的亦或运算之和正好为$i$。其中$1\leq n\leq 10^6$，$K=20$。

可以使用k进制不进位加法来解决这个问题。

参考资料

• 位运算卷积(FWT) & 集合幂级数
• 快速沃尔什变换与k进制FWT