Skip to content

子集卷积(多个数有序) ​

cpp
for(int i=0;i<m;i++)FWT::fwt_or(B[i]);
for(int x=1;x<=m;x++){
    for(int i=0;i<x;i++){
        for(int k=0;k<1<<m;k++){
            B[x][k]+=B[i][k]*B[x-i][k];
            B[x][k]%=mod;
        }
    }
    FWT::ifwt_or(B[x]);
    for(int i=0;i<1<<m;i++){
        int k=__builtin_popcount(i);
        if(x!=k)B[x][i]=0;
    }
    FWT::fwt_or(B[x]);
}
for(int i=0;i<m;i++)FWT::ifwt_or(B[i]);