题解 P6097 【【模板】子集卷积】

EternalAlexander · 2020-02-15 01:02:12 · 题解

记 |S| 表示集合 S 的元素个数，* 表示子集并卷积运算，即 h_i = \sum_{j\cup k = i} f_j \times g_k。

第一个限制 i \cup j=k 容易处理，直接 FWT 计算子集并卷积即可。

考虑第二个限制 i \cap j=\varnothing，等价于 |i|+|j|=|i\cup j|。我们再开一维记录集合中的元素个数即可。

具体地，令 f_{i,j} = \begin{cases}a_j\,(|j|=i)\\0\end{cases}，g_{i,j} = \begin{cases}b_j\,(|j|=i)\\0\end{cases}，有 h_i=\sum_{k=0}^i f_k * g_{i-k}。最后我们所求的答案 c_i = h_{|i|,i}。

复杂度 \mathcal O(n^2 2^n)。供题人开 3s 不知道是什么心态，不明白模板题卡常有什么意义。

#include <bits/stdc++.h>
#define ll long long
const int mod=1e9+9;
int a[22][1<<21],b[22][1<<21],h[22][1<<21],n,t;
int ctz(int x){return __builtin_popcount(x);}

void fwt(int *a,int n,int flag){
    for(int i=1;i<n;i<<=1)
    for(int len=i<<1,j=0;j<n;j+=len)
    for(int k=0;k<i;++k){
        if (flag==1)a[j+k+i]=(a[j+k]+a[j+k+i])%mod;
        else a[j+k+i]=(a[j+k+i]-a[j+k]+mod)%mod;
    }
}

int main(){
    scanf("%d",&n);
    int lim=n;n=1<<n;
    for(int i=0;i<n;++i)
        scanf("%d",&a[ctz(i)][i]);
    for(int i=0;i<n;++i)
        scanf("%d",&b[ctz(i)][i]);
    for(int i=0;i<=lim;++i){
        fwt(a[i],n,1);fwt(b[i],n,1);
    }for(int i=0;i<=lim;++i)
        for(int j=0;j<=i;++j)
            for(int k=0;k<n;++k)h[i][k]=(h[i][k]+(ll)a[j][k]*b[i-j][k]%mod)%mod;
    for(int i=0;i<=lim;++i)fwt(h[i],n,-1);
    for(int i=0;i<n;++i)printf("%d ",h[ctz(i)][i]);
    return 0;
}