Cptraser/ 三月 11, 2019/ 2019.3/ 0 comments

求:

    \[C_k=\sum_{i\oplus j=k}A_i * B_j\]

or运算下:

    \[FWT(A)= \begin{cases} (FWT(A_0),FWT(A_0)+FWT(A_1)) & n>0 \\A & n=0 \end{cases}\]

    \[IFWT(A)= \begin{cases} (IFWT(A_0),IFWT(A_1)-IFWT(A_0)) & n>0 \\A & n=0 \end{cases}\]

and运算下:

    \[FWT(A)= \begin{cases} (FWT(A_0)+FWT(A_1),FWT(A_1)) & n>0 \\A & n=0 \end{cases}\]

    \[IFWT(A)= \begin{cases} (IFWT(A_0)-IFWT(A_1),IFWT(A_1))&n>0 \\A & n=0 \end{cases}\]

xor运算下:

    \[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)= \begin{cases} (\frac{IFWT(A_0)+IFWT(A_1)}{2},\frac{IFWT(A_0)-IFWT(A_1)}{2}) & n>0 \\A & n=0 \end{cases}\]

#include <bits/stdc++.h>
using namespace std;
inline char tc(){
    static char tr[10000],*A=tr,*B=tr;
    return A==B&&(B=(A=tr)+fread(tr,1,10000,stdin),A==B)?EOF:*A++;
}
inline void read(int &x){
    char c;for(;(c=getchar())<48||c>57;);
    for(x=c-'0';(c=getchar())>47&&c<58;x=(x<<1)+(x<<3)+c-'0');
}

const int Mod=998244353,inv2=(Mod+1)>>1;

int N,A[1<<17|17],B[1<<17|17],C[1<<17|17];

void FWT_or(int *A,int Opt){
    for(int i=1;i<(1<<N);i<<=1)
        for(int j=0;j<(1<<N);j+=(i<<1))
            for(int k=0;k<i;k++){
                if(Opt>0)A[i+j+k]=(A[j+k]+A[i+j+k])%Mod;
                else A[i+j+k]=(A[i+j+k]-A[j+k]+Mod)%Mod;
            }
}
void FWT_and(int *A,int Opt){
    for(int i=1;i<(1<<N);i<<=1)
        for(int j=0;j<(1<<N);j+=(i<<1))
            for(int k=0;k<i;k++){
                if(Opt>0)A[j+k]=(A[j+k]+A[i+j+k])%Mod;
                else A[j+k]=(A[j+k]-A[i+j+k]+Mod)%Mod;
            }
}
void FWT_xor(int *A,int Opt){
    for(int i=1;i<(1<<N);i<<=1)
        for(int j=0;j<(1<<N);j+=(i<<1))
            for(int k=0;k<i;k++){
                int x=A[j+k],y=A[i+j+k];
                A[j+k]=(x+y)%Mod,A[i+j+k]=(x-y+Mod)%Mod;
                if(Opt<0)A[j+k]=1ll*A[j+k]*inv2%Mod,A[i+j+k]=1ll*A[i+j+k]*inv2%Mod;
            }
}

int main()
{
    read(N);
    for(int i=0;i<(1<<N);i++)read(A[i]);
    for(int i=0;i<(1<<N);i++)read(B[i]);
    FWT_or(A,1),FWT_or(B,1);
    for(int i=0;i<(1<<N);i++)C[i]=1ll*A[i]*B[i]%Mod;FWT_or(C,-1);
    for(int i=0;i<(1<<N);i++)printf("%d ",C[i]);puts("");
    FWT_or(A,-1),FWT_or(B,-1);
    FWT_and(A,1),FWT_and(B,1);
    for(int i=0;i<(1<<N);i++)C[i]=1ll*A[i]*B[i]%Mod;FWT_and(C,-1);
    for(int i=0;i<(1<<N);i++)printf("%d ",C[i]);puts("");
    FWT_and(A,-1),FWT_and(B,-1);
    FWT_xor(A,1),FWT_xor(B,1);
    for(int i=0;i<(1<<N);i++)C[i]=1ll*A[i]*B[i]%Mod;FWT_xor(C,-1);
    for(int i=0;i<(1<<N);i++)printf("%d ",C[i]);puts("");
    FWT_xor(A,-1),FWT_xor(B,-1);
}

BZOJ4589 HardNim

题面传送门

    \[f[i][j]=\sum f[i-1][j \oplus prime[k]]\]

后一位用FWT加速后,前一位快速幂即可。

#include <cstdio>
#include <cstring>
using namespace std;
 
 
const int Maxn=1e5+5,Mod=1e9+7,inv2=(Mod+1)>>1;
int Prime[Maxn],vis[Maxn],Cnt,N,M,A[Maxn],Ans,len;
void Preface(void){
    for(int i=2;i<Maxn;i++){
        if(!vis[i])Prime[++Cnt]=i;
        for(int j=1;j<=Cnt;j++){
            if(Prime[j]*i>=Maxn)break;
            vis[Prime[j]*i]=1;
            if(!(i%Prime[j]))break;
        }
    }
}
 
void FWT(int *A,int Opt){
    for(int i=1;i<len;i<<=1)
        for(int j=0;j<len;j+=(i<<1))
            for(int k=0;k<i;k++){
                int x=A[j+k],y=A[i+j+k];
                A[j+k]=(x+y)%Mod,A[i+j+k]=(x-y+Mod)%Mod;
                if(Opt<0)A[j+k]=1ll*A[j+k]*inv2%Mod,A[i+j+k]=1ll*A[i+j+k]*inv2%Mod;
            }
}
 
int Ksm(int x,int y){
    int res=1;for(;y;y>>=1,x=1ll*x*x%Mod)if(y&1)res=1ll*res*x%Mod;return res;
}
 
int main()
{
    Preface();
    while(~scanf("%d%d",&N,&M)){Ans=0,len=1;
        while(len<=M)len<<=1;
        memset(A,0,sizeof A);
        for(int i=2;i<=M;i++)if(!vis[i])A[i]=1;
        FWT(A,1);
        for(int i=0;i<len;i++)A[i]=Ksm(A[i],N);
        FWT(A,-1),printf("%d\n",A[0]);
    }
}

HHHOJ185 Monster

题面传送门

    \[f[i][j]=\sum f[i-1][j \oplus 2^k]\]

FWT以后对读入的AfFWT即可。

#include <cstdio>
#include <cstring>
using namespace std;


const int Maxn=1<<18|18,Mod=593119681,inv2=(Mod+1)>>1;
int N,M,A[Maxn],B[Maxn];

void FWT(int *A,int Opt){
    for(int i=1;i<N;i<<=1)
        for(int j=0;j<N;j+=(i<<1))
            for(int k=0;k<i;k++){
                int x=A[j+k],y=A[i+j+k];
                A[j+k]=(x+y)%Mod,A[i+j+k]=(x-y+Mod)%Mod;
                if(Opt<0)A[j+k]=1ll*A[j+k]*inv2%Mod,A[i+j+k]=1ll*A[i+j+k]*inv2%Mod;
            }
}

int Ksm(int x,int y){
    int res=1;for(;y;y>>=1,x=1ll*x*x%Mod)if(y&1)res=1ll*res*x%Mod;return res;
}

int main()
{
    scanf("%d%d",&N,&M);
    for(int i=0;i<=N;i++)A[1<<i]=1;
    N=1<<N;A[0]=1;
    for(int i=0;i<N;i++)scanf("%d",&B[i]);
    FWT(A,1),FWT(B,1);
    for(int i=0;i<N;i++)A[i]=Ksm(A[i],M);
    for(int i=0;i<N;i++)A[i]=1ll*A[i]*B[i]%Mod;
    FWT(A,-1);
    for(int i=0;i<N;i++)printf("%d ",A[i]);
} 

Codeforces662C Binary Table

题面传送门

由于n比较小,考虑列为一个数。

定义Ans_i表示行的反转方案为i(二进制下)时的1的个数,考虑怎样求1的个数。

定义Cnt_i表示列上数为i的列有几个,tmp_i表示i这种列状态最少有几个1,所以tmp_i=min(bits_i,n-bits_i)。因为列可以翻转。(bits_i表示i有几个1)。

则:

    \[Ans_k=\sum_{i\oplus k=j}Cnt_i * tmp_j=\sum_{i\oplus j=k}Cnt_i * tmp_j\]

FWT即可:

#include <cstdio>
#include <string>
#include <iostream>
#include <algorithm>
using namespace std;

const int Maxn=20;
int N,M;
long long Cnt[1<<Maxn|5],tmp[1<<Maxn|5],bits[1<<Maxn|5],Ans=1e9;
string S[Maxn];

void FWT(long long *A,int Opt){
    for(int i=1;i<(1<<N);i<<=1)
        for(int j=0;j<(1<<N);j+=(i<<1))
            for(int k=0;k<i;k++){
                long long x=A[j+k],y=A[i+j+k];
                A[j+k]=x+y,A[i+j+k]=x-y;
                if(Opt<0)A[j+k]/=2,A[i+j+k]/=2;
            }
}

int main()
{
    cin>>N>>M;
    for(int i=0;i<N;i++)cin>>S[i];
    for(int i=0;i<M;i++){
        int tot=0;for(int j=0;j<N;j++)tot+=(S[j][i]-'0')<<j;
        ++Cnt[tot];
    }
    for(int i=1;i<(1<<N);i++)bits[i]=bits[i>>1]+(i&1);
    for(int i=0;i<(1<<N);i++)tmp[i]=min(bits[i],N-bits[i]);//row-reverse
    FWT(Cnt,1),FWT(tmp,1);
    for(int i=0;i<(1<<N);i++)Cnt[i]*=tmp[i];
    FWT(Cnt,-1);
    for(int i=0;i<(1<<N);i++)Ans=min(Ans,Cnt[i]);
    printf("%lld\n",Ans);
}
Share this Post

Leave a Comment

电子邮件地址不会被公开。 必填项已用*标注

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>
*
*