百度不收录网站,如何自己做自己的网站,福建住房与城乡建设网站,哈尔滨网站建设推广目录闲话拿来求什么或与异或闲话
这个比FFT简单了很多呢#xff0c;#xff0c;大概是我可以学懂的水平#xff01;
好像是叫 快速沃尔什变换 #xff1f;
拿来求什么
以 FFT 来类比。我们 FFT 可以在 O(nlogn)\mathrm{O(nlogn)}O(nlogn) 的复杂度下实现求解#xff1…
目录闲话拿来求什么或与异或闲话
这个比FFT简单了很多呢大概是我可以学懂的水平
好像是叫 快速沃尔什变换
拿来求什么
以 FFT 来类比。我们 FFT 可以在 O(nlogn)\mathrm{O(nlogn)}O(nlogn) 的复杂度下实现求解
Ck∑ijkAi×BjC_k\sum_{i jk} A_i \times B_j Ckijk∑Ai×Bj
那么 FWT 的作用就是再 O(nlogn)\mathrm{O(nlogn)}O(nlogn) 的时间复杂度下面求解
Ck∑i⊕jkAi×BjC_k\sum_{i \oplus jk} A_i \times B_j Cki⊕jk∑Ai×Bj
其中的 ⊕\oplus⊕ 是位运算异或的意思。 FWT 应该是支持 ⊕\oplus⊕、∣|∣、 \ 三种位运算的。
然后就准备开始讲这三种位运算分别对应的算法。
或
我们定义 FWT(A)i∑j∣iiAj\mathrm{FWT(A)_i}\sum_{j|ii} A_jFWT(A)i∑j∣iiAj。根据定义可以知道 FWT(A)\mathrm{FWT(A)}FWT(A) 是一个由 AAA 构造出来的多项式。先不管如何构造我们考虑 FWT(A)\mathrm{FWT(A)}FWT(A) 有什么用。我们发现
FWT(A)×FWT(B)\mathrm{FWT(A)} \times \mathrm{FWT(B)}FWT(A)×FWT(B) ∑i0FWT(A)i×FWT(B)i\sum_{i0} \mathrm{FWT(A)_i} \times \mathrm{FWT(B)_i}i0∑FWT(A)i×FWT(B)i ∑i0(∑j∣iiAj×∑k∣iiBk)\sum_{i0} ( \sum_{j|ii} A_j \times \sum_{k|ii} B_ k)i0∑(j∣ii∑Aj×k∣ii∑Bk)
∑i0∑(j∣k)∣iiAj×Bk\sum_{i0} \sum_{(j|k)|ii} A_j \times B_ ki0∑(j∣k)∣ii∑Aj×Bk
∑i0∑(j∣k)∣iiCi\sum_{i0} \sum_{(j|k)|ii} C_ii0∑(j∣k)∣ii∑Ci FWT(C)\mathrm{FWT(C)}FWT(C)
所以我们发现可以在 O(n)\mathrm{O(n)}O(n) 的时间复杂度下实现由 A,BA,BA,B 到 CCC 的转换。所以现在的问题就是如何在 O(nlogn)\mathrm{O(nlogn)}O(nlogn) 及以下的时间复杂度中求出 FWT(A)\mathrm{FWT(A)}FWT(A) 。
考虑分治。假设 AAA 有 2n2^n2n 项那么 A0A_0A0 表示 AAA 的前 2n−12^{n-1}2n−1 A1A_1A1 表示 AAA 的后 2n−12^{n-1}2n−1 项。
然后就可以得到一个崭新的转移
FWT(A){FWT(A0),FWT(A1)FWT(A0)n≥1An0\mathrm{FWT(A)}\begin{cases}{\mathrm{FWT(A_0)},\mathrm{FWT(A_1)}\mathrm{FWT(A_0)}}{n\geq 1}\\{A}{n0}\end{cases}FWT(A){FWT(A0),FWT(A1)FWT(A0)An≥1n0
这个 ,可以理解成把两个多项式拼起来。
如何理解这个式子呢n0n0n0 的边界很好理解问题在上面一个式子。
你考虑 A0A_0A0 和 A1A_1A1 的区别在 AAA 中且在 A0A_0A0中 的项的下标的最高位一定是 0 在 AAA 中且在 A1A_1A1中 的项的下标的最高位一定是 1
所以你发现从 A0A_0A0 和 A1A_1A1 向 AAA 中只有可能是 A0A_0A0 所在的项给 A1A_1A1 所在的项做贡献。
所以就可以做到 O(nlogn)\mathrm{O(nlogn)}O(nlogn) 的时间复杂度实现从 AAA 到 FWT(A)\mathrm{FWT(A)}FWT(A) 的转换了。
但是还需要实现从 FWT(A)\mathrm{FWT(A)}FWT(A) 到 AAA 的转换也就是逆转换。
你感性理解一下大概就是 A_0 会影响的两个位置其中一个只有 A_0 另一个是 A_0A_1 所以设 x_0 为改变的第一个位置 x_1 为改变的第二个位置那么有 xA0xA_0xA0 和 yA0A1yA_0A_1yA0A1 。现在是知道了 x 和 y 所以 A0xA_0xA0xA1y−A0y−xA_1y-A_0y-xA1y−A0y−x
那么关于 或运算 的 FWT 就可以实现了
void OR(ll *a,int n,int op){ //op1是顺转换op-1是逆转换for(int mid1;midn;mid1) for(int lenmid1,j0;jn;jlen) for(int ij;ijmid;i)a[imid](a[imid]a[i]*opMod)%Mod;
}与
这个和 或 差不多但是注意到只有 A1A_1A1 可以向 A0A_0A0 贡献所以反过来。
void AND(ll *a,int n,int op){for(int mid1;midn;mid1) for(int lenmid1,j0;jn;jlen) for(int ij;ijmid;i)a[i](a[i]a[imid]*opMod)%Mod;
}异或
这个可能要麻烦一点。
异或本身并不好统一的下标之间的关联。什么意思呢对于 或 我们可以很清楚的发现对于所有情况都是 A0A_0A0 向 A1A_1A1 做贡献对于 与所有情况都是 A1A_1A1 向 A0A_0A0 做贡献。但是异或并不满足这样的性质。所以需要考虑一种构造 FWT\mathrm{FWT}FWT 的方式使得 A0A_0A0 和 A1A_1A1 的做贡献方式是一成不变的。
那么考虑怎么找到构造方式。
