zcmimi's blog

给定序列A,B,设

C_i=\sum_{j\oplus k=i}A_j \times B_k

分别当\oplusor,and,xor时求出C

思想

\text{fwt}_A为对A进行快速沃尔什变换后的序列

A\rightarrow \text{fwt}_AB\rightarrow \text{fwt}_B的复杂度为\mathcal O(n\log n)

\text{fwt}_C=\text{fwt}_A * \text{fwt}_B的复杂度为\mathcal O(n)

\text{fwt}_C \rightarrow C的复杂度为\mathcal O(n\log n)

OR

C_i=\sum_{j|k=i}A_j \times B_k

构造\displaystyle {\text{fwt}_A}_i=\sum_{j|i}A_j,则

\begin{aligned} &\quad \text{fwt}_A*\text{fwt}_B\\ &=\sum_{j|i=i}\sum_{k|i=i}A_jB_k\\ &=\sum_{(j|k)|i=i}A_jB_k\\ &=\sum_{(j|k)=i}A_jB_k\\ &=\text{fwt}_C \end{aligned}

A\rightarrow \text{fwt}_A也就是求\displaystyle {\text{fwt}_A}_i=\sum_{j|i}A_j

A0表示A中下标最高位为0的部分,A1表示A中下标最高位为1的部分

\text{fwt}_A=\text{mg}(\text{fwt}_{A0},\text{fwt}_{A0}+\text{fwt}_{A1})

(这里的\text{mg}表示拼接序列,+表示对于位置相加)

反过来\text{fwt}_A\rightarrow A就是

A=\text{mg}(A0,A1-A0)

AND

与OR同理

\text{fwt}_A=\text{mg}(\text{fwt}_{A0}+\text{fwt}_{A1},\text{fwt}_{A1})

反过来

A=\text{mg}(A0-A1,A1)

XOR

x\otimes y表示x\&y在二进制下1的个数为奇数还是偶数

满足 (i\otimes j) ~ \text{xor} ~ (i\otimes k)=i\otimes (j ~ \text{xor} ~ k)

\displaystyle \text{fwt}_{A_i}=\sum_{i\oplus j=0} A_j - \sum_{i\oplus j=1} A_j

则有

\begin{aligned} &\quad \text{fwt}_A * \text{fwt}_B\\ &=(\sum_{i\oplus j=0} A_j - \sum_{i\oplus j=1} A_j)(\sum_{i\oplus j=0} B_j - \sum_{i\oplus j=1} B_j)\\ &=(\sum_{i\oplus j=0} A_j)(\sum_{i\oplus j=0} B_j)-(\sum_{i\oplus j=0} A_j)(\sum_{i\oplus j=1} B_j)-(\sum_{i\oplus j=1} A_j)(\sum_{i\oplus j=0} B_j)+(\sum_{i\oplus j=1} A_j)(\sum_{i\oplus j=1} B_j)\\ &=\sum_{i\otimes (j~\text{xor}~k)=0}a_jb_k - \sum_{i\otimes (j~\text{xor}~k)=1}a_jb_k\\ &=\text{fwt}_C \end{aligned}

所以

\text{fwt}_A=\text{mg}(\text{fwt}_{A0}+\text{fwt}_{A1},\text{fwt}_{A0}-\text{fwt}_{A1})

反过来

a=\text{mg}(\frac{A0+A1}2,\frac{A0-A1}2)

#include<bits/stdc++.h>
const int N=1<<17,P=998244353;
int n,A[N],B[N],C[N],a[N],b[N];
void cp(){memcpy(a,A,n<<2),memcpy(b,B,n<<2);}
void mul(){for(int i=0;i<n;++i)C[i]=1ll*a[i]*b[i]%P;}
void op(){for(int i=0;i<n;++i)printf("%d ",C[i]);putchar('\n');}
void mod(int&x){if(x>=P)x-=P;}
void OR(int*f){
    for(int k=1;k<n;k<<=1)
        for(int i=0;i<n;i+=k<<1)
            for(int j=0;j<k;++j)
                mod(f[i+j+k]+=f[i+j]);
}
void IOR(int*f){
    for(int k=1;k<n;k<<=1)
        for(int i=0;i<n;i+=k<<1)
            for(int j=0;j<k;++j)
                mod(f[i+j+k]+=P-f[i+j]);
}
void AND(int*f){
    for(int k=1;k<n;k<<=1)
        for(int i=0;i<n;i+=k<<1)
            for(int j=0;j<k;++j)
                mod(f[i+j]+=f[i+j+k]);
}
void IAND(int*f){
    for(int k=1;k<n;k<<=1)
        for(int i=0;i<n;i+=k<<1)
            for(int j=0;j<k;++j)
                mod(f[i+j]+=P-f[i+j+k]);
}
void XOR(int*f){
    for(int k=1;k<n;k<<=1)
        for(int i=0;i<n;i+=k<<1)
            for(int j=0;j<k;++j){
                int t=f[i+j];
                mod(f[i+j]+=f[i+j+k]),
                mod(f[i+j+k]=t-f[i+j+k]+P);
            }
}
int i2=499122177;
void IXOR(int*f){
    for(int k=1;k<n;k<<=1)
        for(int i=0;i<n;i+=k<<1)
            for(int j=0;j<k;++j){
                int t=f[i+j];
                mod(f[i+j]+=f[i+j+k]),
                mod(f[i+j+k]=t-f[i+j+k]+P);
                f[i+j]=1ll*i2*f[i+j]%P,
                f[i+j+k]=1ll*i2*f[i+j+k]%P;
            }
}
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);
    cp(),OR(a),OR(b),mul(),IOR(C),op();
    cp(),AND(a),AND(b),mul(),IAND(C),op();
    cp(),XOR(a),XOR(b),mul(),IXOR(C),op();
}
快速沃尔什变换(FWT)
comment评论
Search
search