一般形式

类比FFT,构造线性变换

于是设 c(i,j)c(i,j) 为变换系数,即 A[j]FWT(A) 的贡献系数。

FWT(A)[i]=n1j=0c(i,j)Aj

可证 c(i,j)c(i,k)=c(i,jk) 证明略

另外,由于位运算每一位的独立性, c(i,j) 也有一个重要性质: 可以分位考虑。

设二进制数 a 的每一位分别为 : a0,a1,a2

则有 c(i,j)=c(i0,j0)c(i1,j1)c(i2,j2) 就是把每一位的变换系数乘起来。

利用分治求解

设位矩阵为 c=[c(0,0)c(0,1)c(1,0)c(1,1)]

对于某位运算构造出满足条件的可逆矩阵即可(理论上如此233)

任意位运算卷积

题目链接

题解链接

题目给你每一位的位运算,求卷积

下面对题解进行简单的翻译,(假装我已经懂了

20210405翻译初稿

定义下标从 0 开始.定义一个函数集合 Fk,函数接收两个 [0,k) 的整数参数,返回值是 [0,k) 的整数.
我们叫 k×k 的矩阵三元组 (A,B,C)fFk 的一个 convolution triple ,前提是: C 是非退化矩阵(非异矩阵|满秩矩阵),并且该函数对于任意两个 k 维向量 x,y 执行以下过程

  • 定义向量 p=Ax,q=By
  • 定义向量 rp,q 的点乘(内积)
  • 返回 z=C1r

返回 f-convolution, i. e. zs=f(i,j)=sxiyi

现在对于给定的 bitwise-independent function(每位独立位运算) 我们想找到一个 convolution triple 使得卷得够快

对于给定函数 fFk 怎么检查这三个矩阵是否组成 convolution triple 呢?
必要的条件是:对于所有只有一个 1 其他都是 0 的向量,这个卷积应该是正确的
如果 x 只有一个非零元素 xi=1,y 只有一个非零元素 yj=1,那么z也应该只有一个非零元素zf(i,j)=1.满足这个条件就够了因为 linearity of the convolution (卷积的线性?啥特征)

如果 A=aij,B=bij,C=cij, 上述条件可以重写作: C 必须是非退化矩阵,并且对于所有 i,j,s0,1,,k1,应满足 asibsj=cs,f(i,j)

现在我们可以尝试解决 n=1 的情况,其中一种方法是对于任意二进制运算找到一个 convolution triple, 即枚举所有元素为 1,0,1 的矩阵三元组.事实证明对于所有 16 种运算我们都可以找到对应的矩阵.(注意:我们不能像做某些特殊的卷积那样假设 A=B=C, 因为对于函数 f(x,y)=0 并没有满足的三元组)

假设有一个矩阵 X=xij of size a, Y=yij of size b. 把 XY 的结果表示为 Z=zij of size ab, zbi+j,bk+l=xikyjl,(0i,ka,0j,lb) (换而言之,就是 a2 矩阵 Y 放到一个矩阵 X 并乘上来自 X 对应的系数) (in other words, it’s just a2 matrices Y put into a matrix X and multiplied by corresponding coefficients from X)

我们可以证明(通过检查上述条件)如果(A1,B1,C1)fFa 的一个 convolution triple, (A2,B2,C2)gFb 的一个 convolution triple, 那么 (A1A2,B1B)2,C1C2)hFab 的一个 convolution triple, h(bx1+x2,by1+y2)=bf(x1,y1)+g(x2,y2).我们也可以证明如果 C1,C2 都是非退化矩阵, 那么 C1C2 是非退化矩阵

因此我们只需要对于所有给定的函数 fi 求出 convolution triples (Ai,Bi,Ci),那么 (A,B,C)=(An1A0,Bn1B0,Cn1C0) 就是一个原函数(运算)的 convolution triple

剩下的事情就是对 A,B,C1 的快速乘法运算.因为所有这些矩阵都是 2×2 的矩阵, A(orB) 乘上向量 v 的过程可以用雷同 FFT 的做法,只有以下差别:当我们改变下标 v[i]v[i+2k],我们应该把矩阵 Ak 运用到他们而不是蝴蝶变换 i. e.

(vnew[i]vnew[i+2k])=Ak(vold[i]vold[i+2k])

当把 C1 乘上一个向量,我们可以类似上面过程反一下

总的时间复杂度是 O(2nn)

另一种解题方法是只使用 XOR and AND/OR 的卷积,因为其他二进制函数既可以单独处理,也可以取反简化为这三个函数,也存在 O(3n)的解法但是不允许其通过此题

参考资料

2020-2021 Winter Petrozavodsk Camp, Belarusian SU Contest (XXI Open Cup, Grand Prix of Belarus)

我的板子

位运算卷积(FWT) & 集合幂级数

洛谷P4717

K 进制 FWT / 高维多项式乘法 略记