标签：... 卷积 笔记 int 枚举 子集 交集
- 如果没有交集的情况，就可以做或运算卷积
- 考虑交集，没有交集=大小和相同
- 依次考虑集合的大小为0,1,...,n
- 对每种情况，构造长度为(1<<n)的集合幂级数，只对size=i赋值
- 枚举答案中集合的大小为0,1,...,n
- 对每个i,枚举f中的贡献是(j),g中的贡献是(i-j)
- 让(j)和（i-j）做或运算卷积，答案一定合法
- 现在的复杂度是O(\(n^2\)n\(2^n\))，利用FWT的正逆变换都是线性的，就能够做到O(\(n^2\)*\(2^n\))
点击查看代码
//子集卷积
#include <bits/stdc++.h>
using namespace std;
const int mod=1000000009;
int n;
int f[21][(1<<20)],g[21][(1<<20)],a[(1<<20)],b[(1<<20)],h[21][(1<<20)];
int len[(1<<20)];
int lowbit(int n)
{
return n&(-n);
}
int calc(int x)
{
int cnt=0;
while(x)
{
x-=lowbit(x);
cnt++;
}
return cnt;
}
void FWTor(int *a,int n,int type)
{
for(int x=2;x<=n;x<<=1)
{
int k=(x>>1);
for(int i=0;i<n;i+=x)
{
for(int j=0;j<k;j++)
{
(a[i+j+k]+=(a[i+j]*type))%=mod;
}
}
}
}
void pre()
{
for(int i=0;i<=n;i++)
{
for(int j=0;j<(1<<n);j++)
{
f[i][j]=(len[j]==i)*a[j];
g[i][j]=(len[j]==i)*b[j];
}
FWTor(f[i],(1<<n),1);
FWTor(g[i],(1<<n),1);
}
}
void Or(int k,int l)
{
for(int i=0;i<(1<<n);i++)
{
h[k+l][i]=(h[k+l][i]+1ll*f[k][i]*g[l][i]%mod)%mod;
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin>>n;
for(int i=0;i<(1<<n);i++)
{
cin>>a[i];
}
for(int i=0;i<(1<<n);i++)
{
cin>>b[i];
}
for(int i=0;i<(1<<n);i++)
{
len[i]=calc(i);
}
/*
for(int i=0;i<(1<<n);i++)
{
int res=1ll*f[0]*g[i]%mod;
for(int j=i;j;j=(j-1)&i)
{
res=(res+1ll*f[j]*g[i-j]%mod)%mod;
}
cout<<res<<' ';
}
cout<<endl;
*/
//枚举子集的做法
//O(sigma(c(n,i)*2^i))=O(3^n)
pre();
for(int i=0;i<=n;i++)
{
for(int j=0;i+j<=n;j++)
{
Or(i,j);
}
}
for(int i=0;i<=n;i++)
{
FWTor(h[i],(1<<n),-1);
}
for(int i=0;i<(1<<n);i++)
{
cout<<(h[len[i]][i]+mod)%mod<<' ';
}
cout<<endl;
return 0;
}
标签：...,
卷积,
笔记,
int,
枚举,
子集,
交集
From： https://www.cnblogs.com/watersail/p/18401154