FWT

· · 个人记录

或

fwt[a]_i = \sum_{j|i=i}a_j

FWT: fwt[a]=merge(fwt[a_0],fwt[a_0]+fwt[a_1])

IFWT: a=merge(a_0,a_1−a_0)

异或

定义 x\otimes y=\text{popcount}(x \& y) \bmod 2，其中 \text{popcount} 表示「二进制下 1 的个数」。

满足 (i \otimes j) \operatorname{xor} (i \otimes k) = i \otimes (j \operatorname{xor} k)。

构造 fwt[a]_i = \sum_{i\otimes j = 0} a_j - \sum_{i\otimes j = 1} a_j。

FWT: fwt[a]=merge(fwt[a_0]+fwt[a_1],fwt[a_0]-fwt[a_1])

IFWT: a=merge(\frac{a_0+a_1}{2},\frac{a_1−a_0}{2})

#include<bits/stdc++.h>
using namespace std;
const int maxn=(1<<17)+100;
const int mod=998244353;
int read()
{
    int ans=0;bool f=0;char ch=getchar();
    while(ch<'0' or ch>'9'){if(ch=='-')f=1;ch=getchar();}
    while(ch>='0' and ch<='9'){ans=(ans<<1)+(ans<<3)+(ch^48);ch=getchar();}
    return f?~ans+1:ans;
}
int n,a[maxn],b[maxn],c[maxn],ax[maxn],bx[maxn];
inline int M(long long x)
{
    return x>=mod?x%mod:x<0?(x%mod+mod)%mod:x;
}
void fwtor(int a[],int type)
{
    for(int i=1;i<=n;++i)
    for(int j=0;j<(1<<n);j+=(1<<i))
    for(int k=0;k<(1<<i-1);++k)
    a[j|k|(1<<i-1)]=M(1ll*a[j|k]*type+a[j|k|(1<<i-1)]);
}
void fwtand(int a[],int type)
{
    for(int i=1;i<=n;++i)
    for(int j=0;j<(1<<n);j+=(1<<i))
    for(int k=0;k<(1<<i-1);++k)
    a[j|k]=M(1ll*a[j|k|(1<<i-1)]*type+a[j|k]);
}
void fwtxor(int a[],int type)
{
    for(int i=1;i<=n;++i)
    for(int j=0;j<(1<<n);j+=(1<<i))
    for(int k=0;k<(1<<i-1);++k)
    {
        int x,y;
        x=M(1ll*(a[j|k]+a[j|(1<<i-1)|k])*type);
        y=M(1ll*(a[j|k]-a[j|(1<<i-1)|k])*type);
        a[j|k]=x,a[j|(1<<i-1)|k]=y;
    }
}
int main()
{
    n=read();
    for(int i=0;i<(1<<n);++i)
    a[i]=read();
    for(int i=0;i<(1<<n);++i)
    b[i]=read();
    memcpy(ax,a,sizeof a),memcpy(bx,b,sizeof b);
    fwtor(ax,1),fwtor(bx,1);
    for(int i=0;i<(1<<n);++i)
    c[i]=M(1ll*ax[i]*bx[i]);
    fwtor(c,-1);
    for(int i=0;i<(1<<n);++i)
    printf("%d ",c[i]);printf("\n");
    memcpy(ax,a,sizeof a),memcpy(bx,b,sizeof b);
    fwtand(ax,1),fwtand(bx,1);
    for(int i=0;i<(1<<n);++i)
    c[i]=M(1ll*ax[i]*bx[i]);
    fwtand(c,-1);
    for(int i=0;i<(1<<n);++i)
    printf("%d ",c[i]);printf("\n");
    memcpy(ax,a,sizeof a),memcpy(bx,b,sizeof b);
    fwtxor(ax,1),fwtxor(bx,1);
    for(int i=0;i<(1<<n);++i)
    c[i]=M(1ll*ax[i]*bx[i]);
    fwtxor(c,(mod+1)>>1);
    for(int i=0;i<(1<<n);++i)
    printf("%d ",c[i]);printf("\n");
    return 0;
}