柒葉灬 的博客

柒葉灬 的博客

FWT

posted on 2019-09-26 16:34:18 | under 算法学习 |

FWT


FWT的模数不需要有原根!1e9+7这样的也可以用FWT!!!

FWT快速幂时,中间不用IFWT就行了,最后IFWT一次就行了

$C_{i\ opt \ j}=A_i*B_j $


运算符是与

void FWT_and(int *A,int type){
    for(int i=1;i<limit;i<<=1)
        for(int j=0;j<limit;j+=i<<1)
            for(int k=0;k<i;k++)
                add(A[j+k],A[j+k+i]*type);
}

也可以写成高维后缀和的形式

void FWT_and(int *A,int type){
    for(int i=0;i<l;i++)
        for(int j=0;j<limit;j++)
            if(1<<i&j)add(A[j^1<<i],A[j]*type);
}

运算符是或

void FWT_or(int *A,int type){
    for(int i=1;i<limit;i<<=1)
        for(int j=0;j<limit;j+=i<<1)
            for(int k=0;k<i;k++)
                add(A[j+k+i],A[j+k]*type);
}

也可以写成高维前缀和

void FWT_or(int *A,int type){
    for(int i=0;i<l;i++)
        for(int j=0;j<limit;j++)
            if(1<<i&j)add(A[j],A[j^1<<i]*type);
}

运算符是亦或

void FWT_xor(int *A,int type){
    for(int i=1;i<limit;i<<=1){
        for(int j=0;j<limit;j+=i<<1){
            for(int k=0;k<i;k++){
                int x=A[j+k],y=A[j+k+i];
                A[j+k]=(x+y)%P;
                A[j+k+i]=(x-y+P)%P;
                if(type==-1){
                    A[j+k]=1LL*A[j+k]*inv2%P;
                    A[j+k+i]=1LL*A[j+k+i]*inv2%P;
                }
            }
        }
    }
}