luogu P6097 子集卷积 FST FWT

LINK：子集卷积

学了1h多 终于看懂是怎么回事了(题解写的不太清楚 翻了好几篇博客才懂

一个需要用到的性质 二进制位为1个数是i的二进制数s 任意两个没有子集关系。挺显然。

而FST就是利用这个性质靠FWT做的。

直接说做法：

定义\(f_{i,s}\)表示|s|为i状态为s的值.

对于另一个g数组也同时定义。设答案为h.

那么有 \(h_{i,s}=\sum_{j\in s}f_{|j|,j}\cdot g_{|j xor s|,j xor s}\)

暴力做这个还是\(3^n\)

考虑不枚举子集j 而是直接枚举子集的大小j 那么转移的s有很多 我们将其压缩 FWT_or 来做。

那么式子变成 \(h_{i,s}=\sum_{j=1}^i f_{j,s}\cdot g_{j,s}\)

容易发现会有重复 此时 再对\(h_i\)做IFWT即可。

正确性利用前面提到的性质+FWT的性质可得.

const int MAXN=300010,GG=3;
int n,maxx;
int sum[1<<20];
int a[22][1<<20],b[22][1<<20],f[22][1<<20];
inline int add(int x,int y){return x+y>=mod?x+y-mod:x+y;}
inline int mux(int x,int y){return x-y<0?x-y+mod:x-y;}
inline void FWT(int *a)
{
	for(int len=2;len<=maxx+1;len=len<<1)
	{
		int mid=len>>1;
		for(int j=0;j<=maxx;j+=len)
		{
			for(int i=0;i<mid;++i)
			{
				a[i+j+mid]=add(a[i+j+mid],a[i+j]);
			}
		}
	}
}
inline void IFWT(int *a)
{
	for(int len=2;len<=maxx+1;len=len<<1)
	{
		int mid=len>>1;
		for(int j=0;j<=maxx;j+=len)
		{
			for(int i=0;i<mid;++i)
			{
				a[i+j+mid]=mux(a[i+j+mid],a[i+j]);
			}
		}
	}
}
int main()
{
	freopen("1.in","r",stdin);
	get(n);maxx=1<<n;--maxx;
	rep(0,maxx,i)sum[i]=sum[i>>1]+(i&1),get(a[sum[i]][i]);
	rep(0,maxx,i)get(b[sum[i]][i]);
	rep(0,n,i)FWT(a[i]),FWT(b[i]);
	rep(0,n,i)
	{
		rep(0,maxx,s)rep(0,i,j)f[i][s]=add(f[i][s],(ll)a[j][s]*b[i-j][s]%mod);
		IFWT(f[i]);
	}
	rep(0,maxx,i)put_(f[sum[i]][i]);return 0;
}

luogu P6097 子集卷积 FST FWT

原文：https://www.cnblogs.com/chdy/p/13027596.html