正题

题目链接:https://www.luogu.com.cn/problem/P6097

题目大意

长度为\(2^n\)的序列\(a,b\)求一个\(c\)满足

\[c_k=\sum_{i|j=k,i\&j=\varnothing}a_i\times b_j
\]

解题思路

从炫酷反演魔术过来的，顺便写掉这题

简单的说就是求\(k\)的所有子集和其补集的乘积和。

只有\(i|j=k\)的话就是普通的\(\text{FWT}\)了，但是还有\(i\&j=\varnothing\)这个东西。

一个巧妙的想法是把这个条件转换为\(|i|+|j|=|i\cup j|\)，显然两个之间是充要的。

然后可以把\(a_i\)存在\(f_{ct(i),i}\)这个位置，其中\(ct(i)\)表示\(i\)中\(1\)的个数。同理\(b_i\)存在\(g_{ct(i),i}\)这个位置。

然后就有卷积

\[h_{a,b}=\sum_{i+j=a,x|y=b}f_{i,x}\times g_{j,y}
\]

这个先暴力\(\text{FWT}\)了\(f,g\)然后暴力卷积然后\(\text{IFWT}\)回去就好了。

时间复杂度\(O(n^22^n)\)，不能全开\(\text{long long}\)不然会\(\text T\)的

code

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int N=21,P=1e9+9;

int n,k,ct[1<<N],f[N][1<<N],g[N][1<<N],h[N][1<<N];

void FWT(int *f,int op){

    for(int p=2;p<=n;p<<=1)

        for(int k=0,len=p>>1;k<n;k+=p)

            for(int i=k;i<k+len;i++)

                (f[i+len]+=(f[i]*op+P)%P)%=P;

    return;

}

signed main()

{

    // printf("%d",sizeof(f)>>20);

    scanf("%d",&k);n=(1<<k);

    for(int i=0;i<n;i++){

        if(i)ct[i]=ct[i-(i&-i)]+1;

        scanf("%d",&f[ct[i]][i]);

    }

    for(int i=0;i<n;i++)

        scanf("%d",&g[ct[i]][i]);

    for(int i=0;i<=k;i++)

        FWT(f[i],1),FWT(g[i],1);

    for(int i=0;i<=k;i++)

        for(int j=0;j<=i;j++)

            for(int x=0;x<n;x++)

                (h[i][x]+=1ll*f[j][x]*g[i-j][x]%P)%=P;

    for(int i=0;i<=k;i++)FWT(h[i],-1);

    for(int i=0;i<n;i++)

        printf("%d ",h[ct[i]][i]);

    return 0;

}

巴特西

P6097-[模板]子集卷积

正题

题目大意

解题思路

code

最新文章

热门文章