或卷积:

$C_k=\sum_{i|j=k}A_i*B_j$

写成向量的样子:$A|B=(\sum_{i|j=0}A_i*B_j,\sum_{i|j=1}A_i*B_j,......)$

满足交换和结合律

​ 前一半 后一半

$FWT(A)=\begin{cases}(FWT(A_0),FWT(A_0+A_1)) & n\gt0 \\ A & n=0\end{cases}​$

$IFWT(A)=(IFWT(A_0),IFWT(A_1)-IFWT(A_0))​$

$FWT(A+B)=FWT(A)+FWT(B)$

和卷积:

$C_k=\sum_{i\&j=k}A_i*B_j​$

写成向量的样子:$A\&B=(\sum_{i\&j=0}A_i*B_j,\sum_{i\&j=1}A_i*B_j,......)$

$FWT(A)=\begin{cases}(FWT(A_0+A_1),FWT(A_1)) & n\gt0 \\ A & n=0\end{cases}​$

$IFWT(A)=(IFWT(A_0)-IFWT(A_1),IFWT(A_1))$

异或卷积:

$C_k=\sum_{i\oplus j=k}A_i*B_j​$

$FWT(A)=\begin{cases}(FWT(A_0)+FWT(A_1),FWT(A_0)-FWT(A_1)) & n>0\\A & n=0\end{cases}​$

$IFWT(A)=(\frac{IFWT(A_0)+IFWT(A_1)}{2},\frac{IFWT(A_0)-IFWT(A_1)}{2})$

已证明:...【$FWT(A)\times FWT(B)=FWT(A\oplus B)​$

$FWT(A)\times FWT(B)=FWT(A\&B)$

$FWT(A)\times FWT(B)=FWT(A|B)​$

相关例题:

https://www.luogu.org/problemnew/show/P4717

https://www.luogu.org/problemnew/show/CF662C

模板:

void fwtor(int y[],int op){
    for(int i=2;i<=len;i<<=1){
        for(int p=i/2,j=0;j<len;j+=i){
            for(int k=j;k<j+p;k++){
                y[k+p]=(y[k+p]+y[k]*op+mod)%mod;
            }
        } 
    }
} 
void fwtand(int y[],int op){
    for(int i=2;i<=len;i<<=1){
        for(int p=i/2,j=0;j<len;j+=i){
            for(int k=j;k<j+p;k++){
                y[k]=(y[k]+y[k+p]*op+mod)%mod;
            }
        }
    }
}
void fwtxor(int y[],int op){
    for(int i=2;i<=len;i<<=1){
        for(int p=i>>1,j=0;j<len;j+=i){
            for(int k=j;k<j+p;k++){
                int t1=p[k],t2=p[k+p];
                y[k]=(t1+t2)%mod;y[k+p]=(t1-t2+mod)%mod;
                if(op==-1) y[k]=1ll*y[k]*inv2%mod,y[k+p]=1ll*y[k+p]*inv2%mod;
            } 
        }
    }
}
Last modification:March 23rd, 2019 at 05:52 pm