FWT学习笔记

算法

参考文献

Published

October 17, 2022

Content note — Known errors · 明显错误

FWT 笔记中 AND/OR 卷积的公式和章节标题混用，容易误导。

“AND”小节写的是 i = j | k，这是 OR 卷积形式。
建议重新拆分 OR、AND、XOR 的定义、变换和逆变换，并重新验证代码下标约定。

FWT学习笔记

0.参考文献

参考文献

1.FWT的定义与证明

首先fwt是解决一类二进制下与或非运算的卷积问题的

也就是形如 \[ C_i=\sum_{j\oplus k = i}A_j \times B_k \] 使用fwt可以nlogn的进行计算

但是实际上似乎遇到一些任意进制下且不进位的卷积操作都可以考虑使用这种思想进行处理

1.1 AND

\[ c_i = \sum_{i=j|k}a_jb_k \]

有 \[ j|i=i,k|i=i,(j|k)|i=i \]

因为 \[ (j|k)|j = (j|k),(j|k)|i = (j|k) \]

构造 \[ \begin{aligned} fwt_{ai} &= \sum_{j|i=i}a_j\\ fwt_{bi} &= \sum_{k|i=i}b_k\\ fwt_{ci} &= \sum_{(j|k)|i=i}a_j b_k \end{aligned} \] 有 \[ \begin{aligned} fwt[a]\times fwt[b] &=(\sum_{j|i=i}a[j]))\times(\sum_{k|i=i}b[k])) \\ &=\sum_{j|i=i}\sum_{k|i=i}a_j b_k\\ &=\sum_{(j|k)|i=i}a_j b_k\\ &=fwt[c] \end{aligned} \] 如何以nlogn的复杂度计算fwt & ifwt 令\(a_0\)为a中下标最高位为0的部分，\(a_1\)为a中下标最高位为1的部分

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

1.2 OR >> 证明与AND相同

1.3 XOR

这里构造了不同于OR/AND的变换

定义\(x\otimes y = popcount(x\&y)%2\)

其中\(popcount(x)\)为x在二进制下1的个数

显然该运算满足

\[ (i\otimes j)\ xor\ (i\otimes k)=i\otimes(j\ xor \ k) \]

构造

\[ fwt_{ai} = \sum_{i\otimes j =0}a_jb_k \]

有 \[ \begin{aligned} fwt[a]\times fwt[b]&=(\sum_{i\otimes j =0}a_j-\sum_{i\otimes j =1}a_j)\times(\sum_{i\otimes j =0}b_k-\sum_{i\otimes j =1}b_k)\\ &=(\sum_{i\otimes j=0}a_j)(\sum_{i\otimes k=0}b_k)-(\sum_{i\otimes j=0}a_j)(\sum_{i\otimes k=1}b_k)-(\sum_{i\otimes j=1}a_j)(\sum_{i\otimes k=0}b_k)+(\sum_{i\otimes j=1}a_j)(\sum_{i\otimes k=1}b_k)\\ &=(\sum_{i\otimes(j\ xor\ k)=0}a_jb_k-\sum_{i\otimes(j\ xor\ k)=1}a_jb_k)\\ &=fwt[c] \end{aligned} \] 那么

\[ \begin{aligned} fwt[a]&=merge(fwt[a_0]+fwt[a_1],fwt[a_0]-fwt[a_1])\\ a&=merge(\frac{a_0+a_1}{2},\frac{a_0-a_1}{2}) \end{aligned} \]

2.代码

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
#define int long long
const int INF = 0x3f3f3f3f,MAXN = 1<<17|1,P = 998244353;
int n,inv2=(P+1)>>1;
template <typename _TP>
inline _TP qread(_TP &X){
    char ch=0;int w;X=0;
    while(!isdigit(ch)){w=ch=='-';ch=getchar();}
    while(isdigit(ch)){X=(X<<1)+(X<<3)+(ch^48);ch=getchar();}
    X=w?-X:X;
    return X; 
}
int A[MAXN],B[MAXN],a[MAXN],b[MAXN];
inline void cpy(){
    memcpy(a,A,sizeof(A));
    memcpy(b,B,sizeof(B));
}
inline void mul(){
    for(int i=1;i<=n;i++){
        a[i]=(a[i]*b[i])%P;
    }
}
inline void PRINT(){
    for(int i=1;i<=n;i++){
        cout<<a[i]<<" ";
    }
    cout<<'\n';
}
inline void fwtOr(int *a,const int opt){
    for(int i=1;i<n;i<<=1){
        for(int p=i<<1,j=1;j<=n;j+=p){
            for(int k=0;k<i;k++){
                a[i+j+k]=(a[i+j+k]+a[j+k]*opt+P)%P;
            }
        }
    }
}
inline void fwtAnd(int *a,const int opt){
    for(int i=1;i<n;i<<=1){
        for(int p=i<<1,j=1;j<=n;j+=p){
            for(int k=0;k<i;k++){
                a[j+k]=(a[j+k]+a[i+j+k]*opt+P)%P;
            } 
        } 
    } 
}
inline void fwtXor(int *a,const int opt){
    for(int i=1;i<n;i<<=1){
        for(int p=i<<1,j=1;j<=n;j+=p){
            for(int k=0;k<i;k++){
                int X=a[j+k],Y=a[i+j+k];
                a[j+k]=(X+Y)%P;
                a[i+j+k]=(X+P-Y)%P;
                a[j+k]=(a[j+k]*opt)%P;
                a[i+j+k]=(a[i+j+k]*opt)%P;
            }
        }
    }
}
signed main(){
    qread(n);
    n=1<<n;
    for(int i=1;i<=n;i++){
        qread(A[i]);
    }
    for(int i=1;i<=n;i++){
        qread(B[i]);
    }
    cpy();fwtOr(a,1),fwtOr(b,1),mul(),fwtOr(a,-1),PRINT();
    cpy();fwtAnd(a,1),fwtAnd(b,1),mul(),fwtAnd(a,-1),PRINT();
    cpy();fwtXor(a,1),fwtXor(b,1),mul(),fwtXor(a,inv2),PRINT();
    return 0;
}