泰州网站设计咨询,沈阳个人网站建设选择,五八同城找工作招聘信息,兰州最坑人的装修公司前#xff08;che#xff09;言#xff08;dan#xff09; FWTFWTFWT是个神奇的东西。
然而网上多数讲解多数直接给结论#xff0c;顶多用归纳法证一证。
所以本文会讲解FWTFWTFWT的推导过程。
虽然也用到了构造#xff0c;但是好背得多
参考博客#xff1a;https:/…前che言dan
FWTFWTFWT是个神奇的东西。
然而网上多数讲解多数直接给结论顶多用归纳法证一证。
所以本文会讲解FWTFWTFWT的推导过程。
虽然也用到了构造但是好背得多
参考博客https://www.cnblogs.com/ACMSN/p/11031072.html
能干啥
众所周知FFTFFTFFT求的是
Ck∑ijkAiBjC_k\sum_{ijk}A_iB_jCkijk∑AiBj
而FWTFWTFWT求的是
Ck∑i⊕jkAiBjC_k\sum_{i\oplus jk}A_iB_jCki⊕jk∑AiBj 其中⊕\oplus⊕为逻辑位运算符即amp;,∣,^\amp;,|,\hat{},∣,^
两者思想类似但实际上是两条不同的线。
约定
大写字母A,B,CA,B,CA,B,C表示一个序列多项式下标从000开始到n−1n-1n−1结束
小写字母i,j,ki,j,ki,j,k表示循环变量
AB,A−B,A∗BAB,A-B,A*BAB,A−B,A∗B表示对应位直接相加,相减或相乘
A⊕BA \oplus BA⊕B表示对应的卷积⊕\oplus⊕为amp;,∣,^,×(乘法)\amp;,|,\hat{},\times(乘法),∣,^,×(乘法)
A[i]A[i]A[i]表示序列第iii位
A0,A1A_0,A_1A0,A1表示序列前半部分和后半部分
(A,B)(A,B)(A,B)表示将两个序列拼接在一起
如果涉及了集合运算表示这个数二进制111的位置构成的集合
分析
回忆FFTFFTFFT的过程它的思想是构造一个FFTFFTFFT函数及其逆运算IFFTIFFTIFFT使得
IFFT(FFT(A)∗FFT(B))A×BIFFT(FFT(A)*FFT(B))A \times BIFFT(FFT(A)∗FFT(B))A×B
FWTFWTFWT则构造
IFWT(FWT(A)∗FWT(B))A⊕BIFWT(FWT(A)*FWT(B))A \oplus BIFWT(FWT(A)∗FWT(B))A⊕B
以下都假装NNN是222的整数次幂
先说主要思想构造一个i,ji,ji,j的关系式g(i,j)g(i,j)g(i,j)使得
FWT(A)[i]∑j0n−1g(i,j)A[j]FWT(A)[i]\sum_{j0}^{n-1}g(i,j)A[j]FWT(A)[i]j0∑n−1g(i,j)A[j]
我们想要
FWT(A⊕B)FWT(A)∗FWT(B)FWT(A\oplus B)FWT(A)*FWT(B)FWT(A⊕B)FWT(A)∗FWT(B)
即对于任意的iii
FWT(A⊕B)[i]FWT(A)[i]∗FWT(B)[i]FWT(A\oplus B)[i]FWT(A)[i]*FWT(B)[i]FWT(A⊕B)[i]FWT(A)[i]∗FWT(B)[i]
代入
∑j0n−1g(i,j)((A⊕B)[j])∑j0n−1g(i,j)A[j]∑k0n−1g(i,k)B[k]\sum_{j0}^{n-1}g(i,j)((A \oplus B)[j])\sum_{j0}^{n-1}g(i,j)A[j]\sum_{k0}^{n-1}g(i,k)B[k]j0∑n−1g(i,j)((A⊕B)[j])j0∑n−1g(i,j)A[j]k0∑n−1g(i,k)B[k]
拆开
∑x0n−1g(i,x)∑j⊕kxA[j]∗B[k]∑j0n−1g(i,j)A[j]∑k0n−1g(i,k)B[k]\sum_{x0}^{n-1}g(i,x)\sum_{j\oplus kx}A[j]*B[k]\sum_{j0}^{n-1}g(i,j)A[j]\sum_{k0}^{n-1}g(i,k)B[k]x0∑n−1g(i,x)j⊕kx∑A[j]∗B[k]j0∑n−1g(i,j)A[j]k0∑n−1g(i,k)B[k]
右边可以乘法分配率合并其实就是换个顺序
∑x0n−1g(i,x)∑j⊕kxA[j]∗B[k]∑j0n−1∑k0n−1g(i,j)g(i,k)A[j]B[k]\sum_{x0}^{n-1}g(i,x)\sum_{j\oplus kx}A[j]*B[k]\sum_{j0}^{n-1}\sum_{k0}^{n-1}g(i,j)g(i,k)A[j]B[k]x0∑n−1g(i,x)j⊕kx∑A[j]∗B[k]j0∑n−1k0∑n−1g(i,j)g(i,k)A[j]B[k]
左边更换枚举项
∑j0n−1∑k0n−1g(i,j⊕k)A[j]B[k]∑j0n−1∑k0n−1g(i,j)g(i,k)A[j]B[k]\sum_{j0}^{n-1}\sum_{k0}^{n-1}g(i,j\oplus k)A[j]B[k]\sum_{j0}^{n-1}\sum_{k0}^{n-1}g(i,j)g(i,k)A[j]B[k]j0∑n−1k0∑n−1g(i,j⊕k)A[j]B[k]j0∑n−1k0∑n−1g(i,j)g(i,k)A[j]B[k]
即:
g(i,j⊕k)g(i,j)g(i,k)g(i,j\oplus k)g(i,j)g(i,k)g(i,j⊕k)g(i,j)g(i,k)
我们还需要证一个东西
FWT(AB)FWT(A)FWT(B)FWT(AB)FWT(A)FWT(B)FWT(AB)FWT(A)FWT(B)
对于每个iii
FWT(AB)[i]FWT(A)[i]FWT(B)[i]FWT(AB)[i]FWT(A)[i]FWT(B)[i]FWT(AB)[i]FWT(A)[i]FWT(B)[i]
套定义
∑j0n−1g(i,j)(AB)[j]∑j0n−1g(i,j)A[j]∑j0n−1g(i,j)B[j]\sum_{j0}^{n-1}g(i,j)(AB)[j]\sum_{j0}^{n-1}g(i,j)A[j]\sum_{j0}^{n-1}g(i,j)B[j]j0∑n−1g(i,j)(AB)[j]j0∑n−1g(i,j)A[j]j0∑n−1g(i,j)B[j]
然后很显然 证毕
完结撒花
或
构造
g(i,j∣k)g(i,j)g(i,k)g(i,j | k)g(i,j)g(i,k)g(i,j∣k)g(i,j)g(i,k)
写成集合形式
g(i,j∪k)g(i,j)g(i,k)g(i,j \cup k)g(i,j)g(i,k)g(i,j∪k)g(i,j)g(i,k)
构造g(i,j)[j⊂i]g(i,j)[j \subset i]g(i,j)[j⊂i]即可
实现
FWT(A)[i]∑j⊂iA[j]FWT(A)[i]\sum_{j\subset i}A[j]FWT(A)[i]j⊂i∑A[j]
考虑分治
将一个序列分成左右两部分左边最高位为000 右边最高位为111
对于左边其子集就是上一个的子集
右边再加上左边因为可以不选最高位
即
FWT(A)(FWT(A0),FWT(A0)FWT(A1))FWT(A)(FWT(A_0),FWT(A_0)FWT(A_1))FWT(A)(FWT(A0),FWT(A0)FWT(A1))
只有一项直接返回
逆运算解个方程就行了 {FWT(A)0FWT(A0)FWT(A)1FWT(A0)FWT(A1)\left\{ \begin{aligned} FWT(A)_0 amp; FWT(A_0) \\ FWT(A)_1 amp; FWT(A_0)FWT(A_1) \end{aligned} \right. {FWT(A)0FWT(A)1FWT(A0)FWT(A0)FWT(A1)
{FWT(A0)FWT(A)0FWT(A1)FWT(A)1−FWT(A)0\left\{ \begin{aligned} FWT(A_0) amp; FWT(A)_0 \\ FWT(A_1) amp; FWT(A)_1-FWT(A)_0 \end{aligned} \right. {FWT(A0)FWT(A1)FWT(A)0FWT(A)1−FWT(A)0
即
IFWT(A)(IFWT(A0),IFWT(A1)−IFWT(A0))IFWT(A)(IFWT(A_0),IFWT(A_1)-IFWT(A_0))IFWT(A)(IFWT(A0),IFWT(A1)−IFWT(A0))
与
同理略
FWT(A)(FWT(A0)FWT(A1),FWT(A1))FWT(A)(FWT(A_0)FWT(A_1),FWT(A_1))FWT(A)(FWT(A0)FWT(A1),FWT(A1))
IFWT(A)(IFWT(A0)−IFWT(A1),IFWT(A1))IFWT(A)(IFWT(A_0)-IFWT(A_1),IFWT(A_1))IFWT(A)(IFWT(A0)−IFWT(A1),IFWT(A1))
异或
构造
g(i,j^k)g(i,j)g(i,k)g(i,j \hat{\quad} k)g(i,j)g(i,k)g(i,j^k)g(i,j)g(i,k)
我也不知道怎么想到的构造
g(i,j)(−1)∣i∩j∣g(i,j)(-1)^{|i\cap j|}g(i,j)(−1)∣i∩j∣
用到了异或不会改变111的总数的奇偶性 意识流得证
实现
FWT(A)[i]∑j0n−1(−1)∣i∩j∣A[j]FWT(A)[i]\sum_{j0}^{n-1}(-1)^{|i\cap j|}A[j]FWT(A)[i]j0∑n−1(−1)∣i∩j∣A[j]
仍然分成左右两部分右边表示选择最高位
发现只有两侧都填111的时候会改变∣i∩j∣|i\cap j|∣i∩j∣的奇偶性相当于产生负的贡献。其余都产生正贡献。
即
FWT(A)(FWT(A0)FWT(A1),FWT(A0)−FWT(A1))FWT(A)(FWT(A_0)FWT(A_1),FWT(A_0)-FWT(A_1))FWT(A)(FWT(A0)FWT(A1),FWT(A0)−FWT(A1))
IFWT(A)(IFWT(A0)IFWT(A1)2,IFWT(A0)−IFWT(A1)2)IFWT(A)(\frac{IFWT(A_0)IFWT(A_1)}{2},\frac{IFWT(A_0)-IFWT(A_1)}{2})IFWT(A)(2IFWT(A0)IFWT(A1),2IFWT(A0)−IFWT(A1))
代码
void ForT(int* a,int n,int type)
{for (int len2;len(1n);len1){int midlen1;for (int s0;s(1n);slen)for (int k0;kmid;k){a[smidk](a[smidk]type*a[sk])%MOD;if (a[smidk]0) a[smidk]MOD;}}
}
void FandT(int* a,int n,int type)
{for (int len2;len(1n);len1){int midlen1;for (int s0;s(1n);slen)for (int k0;kmid;k){a[sk](a[sk]type*a[smidk])%MOD;if (a[sk]0) a[sk]MOD;}}
}
void FxorT(int* a,int n,int type)
{for (int len2;len(1n);len1){int midlen1;for (int s0;s(1n);slen)for (int k0;kmid;k){a[sk](a[sk]a[smidk])%MOD;a[smidk](a[sk]-2*a[smidk])%MOD;if (a[smidk]0) a[smidk]MOD;if (type-1) a[sk](ll)a[sk]*INV%MOD,a[smidk](ll)a[smidk]*INV%MOD;}}
}
