一般形式
类比FFT,构造线性变换
于是设 c(i,j)c(i,j) 为变换系数,即 A[j] 对 FWT(A) 的贡献系数。
FWT(A)[i]=n−1∑j=0c(i,j)Aj
可证 c(i,j)c(i,k)=c(i,j⊕k) 证明略
另外,由于位运算每一位的独立性, 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) 是 f∈Fk 的一个 convolution triple ,前提是: C 是非退化矩阵(非异矩阵|满秩矩阵),并且该函数对于任意两个 k 维向量 x,y 执行以下过程
- 定义向量 p=Ax,q=By
- 定义向量 r 是 p,q 的点乘(内积)
- 返回 z=C−1r
返回 f-convolution, i. e. zs=∑f(i,j)=sxiyi
现在对于给定的 bitwise-independent function(每位独立位运算) 我们想找到一个 convolution triple 使得卷得够快
对于给定函数 f∈Fk 怎么检查这三个矩阵是否组成 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,s∈0,1,…,k−1,应满足 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. 把 X◦Y 的结果表示为 Z=zij of size ab, zbi+j,bk+l=xikyjl,(0≤i,k≤a,0≤j,l≤b) (换而言之,就是 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) 是 f∈Fa 的一个 convolution triple, (A2,B2,C2) 是 g∈Fb 的一个 convolution triple, 那么 (A1◦A2,B1◦B)2,C1◦C2) 是 h∈Fab 的一个 convolution triple, h(bx1+x2,by1+y2)=bf(x1,y1)+g(x2,y2).我们也可以证明如果 C1,C2 都是非退化矩阵, 那么 C1◦C2 是非退化矩阵
因此我们只需要对于所有给定的函数 fi 求出 convolution triples (Ai,Bi,Ci),那么 (A,B,C)=(An−1◦⋯◦A0,Bn−1◦⋯◦B0,Cn−1◦⋯◦C0) 就是一个原函数(运算)的 convolution triple
剩下的事情就是对 A,B,C−1 的快速乘法运算.因为所有这些矩阵都是 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])
当把 C−1 乘上一个向量,我们可以类似上面过程反一下
总的时间复杂度是 O(2n⋅n)
另一种解题方法是只使用 XOR and AND/OR 的卷积,因为其他二进制函数既可以单独处理,也可以取反简化为这三个函数,也存在 O(3n)的解法但是不允许其通过此题
参考资料
2020-2021 Winter Petrozavodsk Camp, Belarusian SU Contest (XXI Open Cup, Grand Prix of Belarus)