杭州微信网站建设,app下载网站建设,新手如何做网上销售,怎样制作网站后台文章目录前言解析OR定义变换#xff1a;逆变换代码AND代码XOR定义变换逆变换代码所谓快速沃尔什变换#xff0c;就是快速的沃尔玛什锦专柜变换 #xff08;逃#xff09;
前言
正常卷积的定义#xff1a;ck∑ijkaibjc_k\sum_{ijk}a_ib_jck∑ijkaibj。 可以用FFT…
文章目录前言解析OR定义变换逆变换代码AND代码XOR定义变换逆变换代码所谓快速沃尔什变换就是快速的沃尔玛什锦专柜变换 逃
前言
正常卷积的定义ck∑ijkaibjc_k\sum_{ijk}a_ib_jck∑ijkaibj。 可以用FFT或者NTT在 O(nlogn)O(n\log n)O(nlogn) 的复杂度内解决。 然而有些时候我们计算卷积的时候下标关系并不是喜闻乐见的加法而是形如 ck∑i⊕jkaibjc_k\sum_{i\oplus jk}a_ib_jck∑i⊕jkaibj其中的 ⊕\oplus⊕ 是 and or xor 中的一种位运算。 这个时候就需要快速莫比乌斯变换and or和快速沃尔什变换xor同样可以把复杂度降到 O(nlogn)O(n\log n)O(nlogn) 级别。
解析
由于三个运算思想比较类似因此不对两个算法进行特别的区分统称为FWT。 采用类比的思想FFT先把多项式转化为点值表示乘到一起最后再反演回去。 类似的FWT也是先把多项式 A,BA,BA,B 转化为某种变换 FWT(A),FWT(B)\operatorname{FWT}(A),\operatorname{FWT}(B)FWT(A),FWT(B)然后乘起来得到 FWT(C)\operatorname{FWT}(C)FWT(C)最后再反演回去得到 CCC。 根据不同位运算的性质对应的变换有所不同。
OR
定义
求ck∑i∣jkaibjc_k\sum_{i\operatorname{|}jk}a_ib_jck∑i∣jkaibj 考虑或运算有如下性质若 i∣kk,j∣kki|kk,j|kki∣kk,j∣kk那么 (i∣j)∣kk(i|j)|kk(i∣j)∣kk反之亦然。 那么我们就按照这个充要条件设计变换FWTor(A)k∑i∣kkAi\operatorname{FWT}_{or}(A)_k\sum_{i|kk}A_iFWTor(A)k∑i∣kkAi。 自然语言iii 必须是 kkk 的子集才能转移。 考虑两个变换后的多项式逐项系数相乘 FWTor(A)∗FWTor(B)∑k(∑i∣kkai)×(∑j∣kkbj)\operatorname{FWT}_{or}(A)*\operatorname{FWT}_{or}(B)\sum_{k}(\sum_{i|kk}a_i)\times (\sum_{j|kk}b_j)FWTor(A)∗FWTor(B)k∑(i∣kk∑ai)×(j∣kk∑bj) ∑k∑i∣kk∑j∣kkaibj∑k∑(i∣j)∣kkaibjFWTor(C)\sum_{k}\sum_{i|kk}\sum_{j|kk}a_ib_j\sum_{k}\sum_{(i|j)|kk}a_ib_j\operatorname{FWT}_{or}(C)k∑i∣kk∑j∣kk∑aibjk∑(i∣j)∣kk∑aibjFWTor(C) 所以我们就证出了系数直接相乘是对的现在只需要一种快速的变换得到 FWTor\operatorname{FWT}_{or}FWTor 以及将其反演的方法。
变换
还是和FFT类似的考虑分治假设我们要合并两个长度为 2n2^n2n 的序列设它们不同的最高位为1的序列为 A1A_1A1为0的为 A0A_0A0。 考虑 or的性质A0A_0A0 可以转移到 A1A_1A1而 A1A_1A1 无法转移到 A0A_0A0因此有 FWTor(A)(FWTor(A0),FWTor(A0)FWTor(A1))\operatorname{FWT}_{or}(A)(\operatorname{FWT}_{or}(A_0),\operatorname{FWT}_{or}(A_0)\operatorname{FWT}_{or}(A_1))FWTor(A)(FWTor(A0),FWTor(A0)FWTor(A1)) 其中 表示系数逐项相加(f(x),g(x))(f(x),g(x))(f(x),g(x)) 表示把 f(x)f(x)f(x) 和 g(x)g(x)g(x) 顺次写出。
逆变换
那么对应的还原成原序列只需要逆向操作即可 UFWTor(A)(UFWTor(A0),UFWTor(A0)−UFWTor(A1))\operatorname{UFWT}_{or}(A)(\operatorname{UFWT}_{or}(A_0),\operatorname{UFWT}_{or}(A_0)-\operatorname{UFWT}_{or}(A_1))UFWTor(A)(UFWTor(A0),UFWTor(A0)−UFWTor(A1))
代码
写起来非常简洁
void Or(ll *x,int n,int op){for(int l1;ln;l1){for(int st0;stn;stl*2){for(int i0;il;i){ll ux[sti],vx[stli];if(op1) x[sti]u,x[stli](vu)%mod;else x[sti]u,x[stli](vmod-u)%mod;}}}
}AND
和 or 的整个定义、证明几乎都是一样的。 求ck∑ijkaibjc_k\sum_{i\operatorname{\}jk}a_ib_jck∑ijkaibj 与运算有如下性质若 ikk,jkki\kk,j\kkikk,jkk那么 (ij)kk(i\j)\kk(ij)kk反之亦然。 按照这个充要条件设计变换FWTor(A)k∑i∣kkAi\operatorname{FWT}_{or}(A)_k\sum_{i|kk}A_iFWTor(A)k∑i∣kkAi。 自然语言iii 必须是 kkk 的超集才能转移。 后面的证明一模一样变换也可以同理的得到 FWTand(A)(FWTand(A0)FWTand(A1),FWTand(A1))\operatorname{FWT}_{and}(A)(\operatorname{FWT}_{and}(A_0)\operatorname{FWT}_{and}(A_1),\operatorname{FWT}_{and}(A_1))FWTand(A)(FWTand(A0)FWTand(A1),FWTand(A1)) UFWTand(A)(UFWTand(A0)−UFWTand(A1),UFWTand(A1))\operatorname{UFWT}_{and}(A)(\operatorname{UFWT}_{and}(A_0)-\operatorname{UFWT}_{and}(A_1),\operatorname{UFWT}_{and}(A_1))UFWTand(A)(UFWTand(A0)−UFWTand(A1),UFWTand(A1))
代码
void And(ll *x,int n,int op){for(int l1;ln;l1){for(int st0;stn;stl*2){for(int i0;il;i){ll ux[sti],vx[stli];if(op1) x[sti](uv)%mod,x[stli]v;else x[sti](umod-v)%mod,x[stli]v;}}}
}XOR
这个和之前的有所不同。
定义
求ck∑i⊕jkaibjc_k\sum_{i\operatorname{\oplus}jk}a_ib_jck∑i⊕jkaibj 设 d(x)d(x)d(x) 为二进制下 xxx 的1的个数的奇偶性模2的结果。 有性质d(ik)⊕d(jk)d((i⊕j)k)d(i\ k)\oplus d(j\ k)d((i\oplus j)\ k)d(ik)⊕d(jk)d((i⊕j)k)。 证明 由于与运算只考虑 kkk 为1的那些位。如果某一位 i,ji,ji,j 都是1或0那么等号两边的奇偶性都不改变如果某一位 i,ji,ji,j 一个是1一个是0那么等号两边的奇偶性都改变所以等号两遍的奇偶性始终同步改变最后就一定是相等的。
设计 FWTxor(A)k∑i(−1)d(ik)ai\operatorname{FWT}_{xor}(A)_k\sum_{i} (-1)^{d(i\ k)}a_iFWTxor(A)ki∑(−1)d(ik)ai 那么还是尝试逐项相乘 FWTxor(A)∗FWTxor(B)∑k(∑i(−1)d(ik)ai)×(∑j(−1)d(jk)bj)\operatorname{FWT}_{xor}(A)*\operatorname{FWT}_{xor}(B)\sum_k(\sum_{i} (-1)^{d(i\ k)}a_i)\times (\sum_{j} (-1)^{d(j\ k)}b_j)FWTxor(A)∗FWTxor(B)k∑(i∑(−1)d(ik)ai)×(j∑(−1)d(jk)bj) ∑k∑i,j(−1)d(ik)d(jk)aibj∑k∑i,j(−1)d(ik)⊕d(jk)aibj\sum_k\sum_{i,j} (-1)^{d(i\ k)d(j\ k)}a_ib_j\sum_k\sum_{i,j} (-1)^{d(i\ k)\oplus d(j\ k)}a_ib_jk∑i,j∑(−1)d(ik)d(jk)aibjk∑i,j∑(−1)d(ik)⊕d(jk)aibj ∑k∑i,j(−1)d((i⊕j)k)aibjFWTxor(C)\sum_k\sum_{i,j} (-1)^{d((i\oplus j)\ k)}a_ib_j\operatorname{FWT}_{xor}(C)k∑i,j∑(−1)d((i⊕j)k)aibjFWTxor(C) 得证。
变换
还是分治的思想考虑到增加一位后只有下标最高位带1的数贡献到了下标最高位带1的位置时最高位与运算结果为11的个数增加一个奇偶性改变所有的符号都变为相反。其它的转移都不变。 也就是 FWTxor(A)(FWTxor(A0)FWTxor(A1),FWTxor(A0)−FWTxor(A1))\operatorname{FWT}_{xor}(A)(\operatorname{FWT}_{xor}(A_0)\operatorname{FWT}_{xor}(A_1),\operatorname{FWT}_{xor}(A_0)-\operatorname{FWT}_{xor}(A_1))FWTxor(A)(FWTxor(A0)FWTxor(A1),FWTxor(A0)−FWTxor(A1))
逆变换
反过来即可。 FWTxor(A)(FWTxor(A0)FWTxor(A1)2,FWTxor(A0)−FWTxor(A1)2)\operatorname{FWT}_{xor}(A)(\frac{\operatorname{FWT}_{xor}(A_0)\operatorname{FWT}_{xor}(A_1)}{2},\frac{\operatorname{FWT}_{xor}(A_0)-\operatorname{FWT}_{xor}(A_1)}{2})FWTxor(A)(2FWTxor(A0)FWTxor(A1),2FWTxor(A0)−FWTxor(A1))
代码
void Xor(ll *x,int n,int op){for(int l1;ln;l1){for(int st0;stn;stl*2){for(int i0;il;i){ll ux[sti],vx[stli];if(op1) x[sti](uv)%mod,x[stli](umod-v)%mod;else x[sti](uv)%mod*499122177%mod,x[stli](umod-v)%mod*499122177%mod;}}}
}Thanks for reading!
