FWT
背景
类似与\(FFT\),\(FWT\)是在下标位运算为背景的变换
\(FFT\)是利用单位根插值作为变换,而\(FWT\)同样要构造\(FWT(A),IFWT(A)\)
当然\(FWT(A\times B)=FWT(A)\ op \ FWT(B)\)
或
定义\(C=A\times B=\sum\limits_{i=j|k}A_jB_k\)
考虑构造\(FWT(A)_i=\sum\limits_{i=i|j}A_j\)，相当于枚举\(i\)中\(1\)的子集
\(FWT(C)_i=FWT(A)_iFWT(B)_i=\sum\limits_{i=i|j,i=i|k}A_jB_k=\sum\limits_{i=i|{p,p=j|k}}A_jB_k=\sum\limits_{i=i|p}C_p\)
现在问题在于如何求解\(FWT(A)\)
考虑将\(A\)按下标平分为\(A_0,A_1\),当然这里要补全到\(2\)的幂次
我们分别求解\(A_0,A_1\)在他们自己的长度下的\(FWT\)
对于\(A_0\),相对于\(A_1\)它的最高为\(0\),很明显不用考虑这一位,即他的贡献为\(FWT(A_0)\)
对于\(A_1\),最高位为\(1\),它不仅要考虑自己,也要考虑\(A_0\)的贡献即\(FWT(A_0)+FWT(A_1)\)
总上,\(FWT(A)=Merge(FWT(A_0),FWT(A_0)+FWT(A_1))\)
平分\(FWT(A)\)为\(B_0,B_1\)
至于\(IFWT\),\(A_0=IFWT(B_0)\),\(A_1=IFWT(FWT(A_1))=IFWT(B_1-FWT(A_0))=IFWT(B_1)-IFWT(B_0)\)
即\(IFWT(A)=Merge(IFWT(A_0),IFWT(A_1)-IFWT(A_0))\)
与
和或差不多
设计\(FWT(A)_i=\sum\limits_{i=i\&j}A_j\),相当于\(1\)的超集
\(A_0\)可以累加\(A_0,A_1\)的贡献,\(A_1\)只有他自己的
\(FWT(A)=Merge(FWT(A_0)+FWT(A_1),FWT(A_1))\)
\(IFWT(A)=Merage(IFWT(A_0)-IFWT(A_1),IFWT(A_1))\)
异或
这个构造有点奇怪
设\(c(x)\)为\(x\)中\(1\)个数
\(FWT(A)_i=\sum\limits_{j}(-1)^{c(i\&j)}A_j\)
若有个性质\((c(i\&k)\&1)\oplus(c(j\&k)\&1)=(c((i\oplus j)\&k)\&1)\)
具体证明不会
然后考虑\(A\)的前部分,很明显\(A_0,A_1\)的结果是一样的
考虑后半部分,\(A_1\)中\(1\)的个数会增加,则其变负
即\(FWT(A)=Merge(FWT(A_0)+FWT(A_1),FWT(A_0)-FWT(A_1))\)
\(IFWT\)类似与或
\(IFWT(A)=Merge(\dfrac{IFWT(A_0)+IFWT(A_1)}{2},\dfrac{IFWT(A_0)-IFWT(A_1)}{2})\)
#include<bits/stdc++.h>
using namespace std;
const int MOD=998244353;
struct Poly{
vector<int>V;
void FWT_OR(int Lit,int Type)
{
if(Type==1)
{
int len=(1<<Lit);
for(int Len=2;Len<=len;Len<<=1)
{
for(int i=0;i<len;i+=Len)
{
for(int j=i;j<=(i+Len/2)-1;j++)
{
V[j]=V[j];
V[j+(Len/2)]=((long long)V[j]+V[j+(Len/2)])%MOD;
}
}
}
}
else
{
int len=(1<<Lit);
for(int Len=2;Len<=len;Len<<=1)
{
for(int i=0;i<len;i+=Len)
{
for(int j=i;j<=(i+Len/2)-1;j++)
{
V[j]=V[j];
V[j+(Len/2)]=((long long)V[j+(Len/2)]-V[j]+MOD)%MOD;
}
}
}
}
}
void FWT_AND(int Lit,int Type)
{
if(Type==1)
{
int len=(1<<Lit);
for(int Len=2;Len<=len;Len<<=1)
{
for(int i=0;i<len;i+=Len)
{
for(int j=i;j<=(i+Len/2)-1;j++)
{
V[j]=((long long)V[j]+V[j+(Len/2)])%MOD;
}
}
}
}
else
{
int len=(1<<Lit);
for(int Len=2;Len<=len;Len<<=1)
{
for(int i=0;i<len;i+=Len)
{
for(int j=i;j<=(i+Len/2)-1;j++)
{
V[j]=((long long)V[j]-V[j+(Len/2)]+MOD)%MOD;
}
}
}
}
}
void FWT_XOR(int Lit,int Type)
{
int inv2=(MOD-MOD/2);
if(Type==1)
{
int len=(1<<Lit);
for(int Len=2;Len<=len;Len<<=1)
{
for(int i=0;i<len;i+=Len)
{
for(int j=i;j<=(i+Len/2)-1;j++)
{
int x=V[j];
int y=V[j+(Len/2)];
V[j]=((long long)x+y)%MOD;
V[j+(Len/2)]=((long long)x-y+MOD)%MOD;
}
}
}
}
else
{
int len=(1<<Lit);
for(int Len=2;Len<=len;Len<<=1)
{
for(int i=0;i<len;i+=Len)
{
for(int j=i;j<=(i+Len/2)-1;j++)
{
int x=V[j];
int y=V[j+(Len/2)];
V[j]=((long long)x+y)%MOD;
V[j+(Len/2)]=((long long)x-y+MOD)%MOD;
V[j]=((long long)V[j]*inv2)%MOD;
V[j+(Len/2)]=((long long)V[j+(Len/2)]*inv2)%MOD;
}
}
}
}
}
};
Poly Mul_OR(Poly A,Poly B)
{
int Lit=1;
int N=max(A.V.size(),B.V.size());
int now=0;
while(Lit<N)
{
Lit*=2;
now++;
}
while(A.V.size()<Lit)
{
A.V.push_back(0);
}
while(B.V.size()<Lit)
{
B.V.push_back(0);
}
A.FWT_OR(now,1);
B.FWT_OR(now,1);
Poly C;
C.V.clear();
for(int i=0;i<Lit;i++)
{
C.V.push_back(((long long)A.V[i]*B.V[i])%MOD);
}
C.FWT_OR(now,-1);
return C;
}
Poly Mul_AND(Poly A,Poly B)
{
int Lit=1;
int N=max(A.V.size(),B.V.size());
int now=0;
while(Lit<N)
{
Lit*=2;
now++;
}
while(A.V.size()<Lit)
{
A.V.push_back(0);
}
while(B.V.size()<Lit)
{
B.V.push_back(0);
}
A.FWT_AND(now,1);
B.FWT_AND(now,1);
Poly C;
C.V.clear();
for(int i=0;i<Lit;i++)
{
C.V.push_back(((long long)A.V[i]*B.V[i])%MOD);
}
C.FWT_AND(now,-1);
return C;
}
Poly Mul_XOR(Poly A,Poly B)
{
int Lit=1;
int N=max(A.V.size(),B.V.size());
int now=0;
while(Lit<N)
{
Lit*=2;
now++;
}
while(A.V.size()<Lit)
{
A.V.push_back(0);
}
while(B.V.size()<Lit)
{
B.V.push_back(0);
}
A.FWT_XOR(now,1);
B.FWT_XOR(now,1);
Poly C;
C.V.clear();
for(int i=0;i<Lit;i++)
{
C.V.push_back(((long long)A.V[i]*B.V[i])%MOD);
}
C.FWT_XOR(now,-1);
return C;
}
Poly A,B;
int n;
int x;
int main()
{
// freopen("date.in","r",stdin);
scanf("%d",&n);
for(int i=0;i<(1<<n);i++)
{
scanf("%d",&x);
A.V.push_back(x);
}
for(int i=0;i<(1<<n);i++)
{
scanf("%d",&x);
B.V.push_back(x);
}
Poly C=Mul_OR(A,B);
for(int i=0;i<(1<<n);i++)
{
printf("%d ",C.V[i]);
}
printf("\n");
C=Mul_AND(A,B);
for(int i=0;i<(1<<n);i++)
{
printf("%d ",C.V[i]);
}
printf("\n");
C=Mul_XOR(A,B);
for(int i=0;i<(1<<n);i++)
{
printf("%d ",C.V[i]);
}
printf("\n");
return 0;
}