• Welcome to the world's largest Chinese hacker forum

    Welcome to the world's largest Chinese hacker forum, our forum registration is open! You can now register for technical communication with us, this is a free and open to the world of the BBS, we founded the purpose for the study of network security, please don't release business of black/grey, or on the BBS posts, to seek help hacker if violations, we will permanently frozen your IP and account, thank you for your cooperation. Hacker attack and defense cracking or network Security

    business please click here: Creation Security  From CNHACKTEAM

Recommended Posts

快速沃尔什变换(FWT)学习笔记

What 这是啥呀

\ (~ ~ ~ ~ \)快速沃尔什变换也用于解决一些卷积问题。不同的是,它所解决的卷积的下标一般被位运算,用加法代替,所以集合卷积也可以用来表达它所能解决的问题。

\ (~ ~ ~ ~ \)没见识,也就到此为止了。

How 怎么做

\ (~ ~ ~ ~ \)显然暴力卷积的复杂度会猛增,于是我们想到了用\(\operatorname{FFT/NTT}\)使用的方法对多项式进行变换,使相应的项可以分别相乘得到最终的结果。

\ (~ ~ ~ ~ \)换句话说,我们应该为多项式\ (\算符名{FWT(A)}\)构造一个对应规则,使得:\(\算符名{FWT} (a \ oplusb)=\算符名{FWT} (a) \ times \。其中\(\oplus\)是所需的卷积运算。乘法单纯指对应项相乘在这里。

\ (~ ~ ~ ~ \)我们认为下面提到的多项式的长度\(n\)都是\(2\)的幂。

\ (~ ~ ~ ~ \)在讲下面的部分之前,我们再介绍两个符号:

\(,\):表示连接前后的两个多项式系数,如\ (\ {1,1,4 \},\ {5,1,4 \}=\ {1,1,4,5,1,4 \})。(当然,这个例子没有遵守长度必须是2的幂的限制)

\(A_0,A_1\):分别表示多项式的前半部分和后半部分,如for \(A=\{1,1,4,5,1,4\})、\(A_0=\{1,1,4\}\。

\ (~ ~ ~ ~ \)引入符号后,如何构造?利用人类的智力不难获得:

或 FWT

\[\ text { FWT }(A)=1

\left\{\begin{array}{l}

\操作员姓名{FWT}(A_0),\操作员姓名{FWT}(A_0 A_1) n1 \\

An=1

\end{array}\right。

\]

与 FWT

\[\ text { FWT }(A)=1

\left\{\begin{array}{l}

\操作员姓名{FWT}(A_0 A_1),\操作员姓名{FWT}(A_1) n1 \\

An=1

\end{array}\right。

\]

异或 FWT

\[\ text { FWT }(A)=1

\left\{\begin{array}{l}

\操作者姓名{FWT}(A_0 A_1),\操作者姓名{FWT}(A_0-A_1) n1 \

An=1

\end{array}\right。

\]

\ (~ ~ ~ ~ \)当然要减,但显然这种逆运算非常容易推。实际上,我们可以把它看作是解方程。

或 IFWT

\[\ text { IFWT }(A)=1

\left\{\begin{array}{l}

\operatorname{IFWT}(A_0),\ operator name { IFWT }(A _ 1-A _ 0)n1 \

An=1

\end{array}\right。

\]

与 IFWT

\[\ text { IFWT }(A)=1

\left\{\begin{array}{l}

\operatorname{IFWT}(A_0-A_1),\operatorname{IFWT}(A_1) n1 \

An=1

\end{array}\right。

\]

异或 IFWT

\[\ text { IFWT }(A)=1

\left\{\begin{array}{l}

\ operator name { IFWT }(\ frac { A _ 0 A _ 1 } { 2 }),\ operator name { IFWT }(\ frac { A _ 0-A _ 1 } { 2 })n1 \

An=1

\end{array}\right。

\]

复制粘贴太酷了!

Why 为什么它是对的

3>

\(~~~~\) 由于证明过程类似,我们只对或运算的正确性进行证明。

\(~~~~\) 归根结底也就是要证对于或运算:\(\text{FWT(A}\operatorname{or} \text{B)=FWT(A)}\times\text{FWT(B)}\) 。

\(~~~~\) 这一类证明一般使用数学归纳法,因此我们从底层 \(n=1\) 证起:

\[\operatorname{FWT}(A \operatorname{or} B)=A \times B=\operatorname{FWT}(A)\times \operatorname{FWT}(B) \]

\(~~~~\) 而当 \(n>1\) 时考虑在什么情况下或运算会分到后半部分,什么情况下会分到前半部分:

\[\operatorname{FWT}(A \operatorname{or} B) = \operatorname{FWT}[(A_0 \operatorname{or} B_0),(A_0\operatorname{or}B_1)+(A_1 \operatorname{or} B_0)+(A_1 \operatorname{or} B_1)]\\ \]

\(~~~~\) 由定义展开:

\[=\operatorname{FWT}[(A_0 \operatorname{or} B_0)],\operatorname{FWT}[(A_0 \operatorname{or} B_0)+(A_0\operatorname{or}B_1)+(A_1 \operatorname{or} B_0)+(A_1 \operatorname{or} B_1)] \]

\(~~~~\) 这里用到一个猜想:\(\operatorname{FWT(A+B)}=\operatorname{FWT}(A)+\operatorname{FWT}(B)\) ,稍后我们会证明它

\[=\operatorname{FWT}[(A_0 \operatorname{or} B_0)],\operatorname{FWT}[(A_0 \operatorname{or} B_0)]+\operatorname{FWT}[(A_0\operatorname{or}B_1)]+\operatorname{FWT}[(A_1 \operatorname{or} B_0)]+\operatorname{FWT}[(A_1 \operatorname{or} B_1)]\\ \]

\(~~~~\) 把它再用下层结论打开:

\[=[\operatorname{FWT}(A_0)\times \operatorname{FWT}(B_0)],[\operatorname{FWT}(A_0)\times \operatorname{FWT}(B_0)]+[\operatorname{FWT}(A_0)\times \operatorname{FWT}(B_1)]\\+[\operatorname{FWT}(A_1)\times \operatorname{FWT}(B_0)]+[\operatorname{FWT}(A_1)\times \operatorname{FWT}(B_1)] \]

\(~~~~\) 整理一下:

\[=[\operatorname{FWT}(A_0)\times \operatorname{FWT}(B_0)],\operatorname{FWT}(A_0+A_1)\times \operatorname{FWT}(B_0+B_1) \]

\(~~~~\) 不难注意到一个事实:\([\operatorname{FWT}(A)\times \operatorname{FWT(B)}],[\operatorname{FWT}(C)\times \operatorname{FWT}(D)]=[\operatorname{FWT}(A),\operatorname{FWT}(C)]\times [\operatorname{FWT}(B),\operatorname{FWT}(D)]\) 。

\(~~~~\) 故原式可改写为:

\[=[\operatorname{FWT}(A_0),\operatorname{FWT}(A_0+A_1)]\times [\operatorname{FWT}(B_0),\operatorname{FWT}(B_0+B_1)]\\ =\operatorname{FWT}(A)\times \operatorname{FWT}(B) \]

\(~~~~\) 故得证。

\(~~~~\) 但最后还得证我们的猜想:\(\operatorname{FWT(A+B)}=\operatorname{FWT}(A)+\operatorname{FWT}(B)\)

\(~~~~\) 仍然先证 \(n=1\) 的情况:

\[\operatorname{FWT}(A+B)=A+B=\operatorname{FWT}(A)+\operatorname{FWT}(B) \]

\(~~~~\) 然后 \(n>1\) :

\[\operatorname{FWT}(A+B)=\operatorname{FWT}[(A+B)_0],\operatorname{FWT}[(A+B)_0+(A+B)_1]\\ =\operatorname{FWT}(A_0)+\operatorname{FWT}(B_0),\operatorname{FWT}(A_0)+\operatorname{FWT}(B_0)+\operatorname{FWT}(A_1)+\operatorname{FWT}(B_1) \]

\(~~~~\) 仍然用于上面事实类似的方法:

\[=[\operatorname{FWT}(A_0),\operatorname{FWT}(A_0)+\operatorname{FWT}(A_1)]+[\operatorname{FWT}(B_0),\operatorname{FWT}(B_0)+\operatorname{FWT}(B_1)]\\ =\operatorname{FWT}(A)+\operatorname{FWT}(B) \]

\(~~~~\) 至此或运算的正确性得证。

\(~~~~\) 与运算和异或运算类比可得。

Code

查看代码
#include <cstdio>
#include <vector>
#include <algorithm>
#define ll long long
using namespace std;
int n; 
const int MOD=998244353;
inline ll Add(ll a,ll b){return (a+b)%MOD;}
inline ll Dec(ll a,ll b){return (a-b+MOD)%MOD;}
inline ll Mul(ll a,ll b){return 1ll*a*b%MOD;}
ll qpow(ll a,ll b)
{
	ll ret=1;
	while(b)
	{
		if(b&1) ret=ret*a%MOD;
		b>>=1;a=a*a%MOD;
	}
	return ret;
}
int a[500005],b[500005];
int A[500005],B[500005],C[500005];
void Copy(){for(int i=0;i<n;i++) A[i]=a[i],B[i]=b[i];}
void OR(int *S,int op)
{
	if(op==-1) op=MOD-1;
	for(int i=1;i<n;i<<=1)
		for(int j=0;j<n;j+=i<<1)
			for(int k=0;k<i;k++) S[i+j+k]=Add(S[i+j+k],Mul(S[j+k],op));
}
void AND(int *S,int op)
{
	if(op==-1) op=MOD-1;
	for(int i=1;i<n;i<<=1)
		for(int j=0;j<n;j+=i<<1)
			for(int k=0;k<i;k++) S[j+k]=Add(S[j+k],Mul(S[i+j+k],op));
}
void XOR(int *S,int op)
{
	if(op==-1) op=qpow(2,MOD-2);
	for(int i=1;i<n;i<<=1)
	{
		for(int j=0;j<n;j+=i<<1)
		{
			for(int k=0;k<i;k++)
			{
				int x=S[j+k],y=S[i+j+k];
				S[j+k]=Mul(op,Add(x,y)); S[i+j+k]=Mul(op,Dec(x,y));
			}
		}
	}
}
int main() {
	scanf("%d",&n); n=1<<n;
	for(int i=0;i<n;i++) scanf("%d",&a[i]);
	for(int i=0;i<n;i++) scanf("%d",&b[i]);
	Copy(); OR(A,1);  OR(B,1);  for(int i=0;i<n;i++) C[i]=Mul(A[i],B[i]); OR(C,-1);  for(int i=0;i<n;i++) printf("%d ",C[i]);puts("");
	Copy(); AND(A,1); AND(B,1); for(int i=0;i<n;i++) C[i]=Mul(A[i],B[i]); AND(C,-1); for(int i=0;i<n;i++) printf("%d ",C[i]);puts("");
	Copy(); XOR(A,1); XOR(B,1); for(int i=0;i<n;i++) C[i]=Mul(A[i],B[i]); XOR(C,-1); for(int i=0;i<n;i++) printf("%d ",C[i]);puts("");
	return 0;
}
Link to comment
Share on other sites