自动搬运

查看原文

来自洛谷，原作者为

	EternalAlexander 魔力的碎片都不再拥有的少年

搬运于2025-08-24 22:17:23，当前版本为作者最后更新于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;
}