「Codeforces 1034E」Little C Loves 3 III

Codeforces 1034E

题意

给你两个 \(2^n\) 的数组 \(a_0,..,a_{2^n-1}\) 和 \(b_0,..,b_{2^n-1}\)

在模 \(4\) 意义下求子集卷积

\(n\le 21\)

---

做法

显然有 \(\mathcal O(n^2 * 2^n)\) 的暴力子集卷积做法

令 \(A_{S,k}\) 表示对于 \(a\)，集合为 \(S\)，集合大小是 \(k\) 的值，\(B_{S,k}\) 同理

只有 \(A_{S,|S|}=a_S\) 是有效的，其余位置都是无效的

通过限制集合大小来保证转化为集合并卷积之后不会多算

\[f_{X,k}=\sum_{S\cup T=X} \sum_{i+j=k} A_{S,i}B_{T,j}\]

答案就是每个 \(f_{S,|S|}\)

把第二维看成一个形式幂级数，就有

\[f_X(x)=\sum_{S\cup T=X} A_S(x) B_T(x)\]

答案就是 \([x^{|S|}]f_S(x)\)

形式幂级数的加法是 \(\mathcal O(n)\) 的，乘法是 \(\mathcal O(n^2)\) 的，FMT是 \(\mathcal O(n * 2^n)\) 的，总复杂度 \(\mathcal O(n^2 * 2^n)\)，无法通过此题

由于这里模数特殊，考虑把系数压到一个unsigned long long中处理，两位恰好存一个系数

于是我们可以 \(\mathcal O(1)\) 地完成加法和乘法，总复杂度 \(\mathcal O(n * 2^n)\)，可以通过此题

可能会有进位，但是通过分类处理加法和乘法还是可以完成的

事实上这里并不需要考虑进位的影响，因为 \([x^i]A_S(x)\) 和 \([x^j]B_T\) 会贡献到 \([x^{i+j}]f_{S\cup T}\)，这里总是有 \(i+j\ge |S\cup T|\)，我们需要的是 \([x^{|S\cup T|}]f_{S\cup T}\)，进位是不会对最低位产生影响的

所以直接+和*就好了

---

代码

#include<cstdio>
#include<algorithm>
#include<ctype.h>
#include<string.h>
#include<math.h>

using namespace std;
#define ull unsigned long long

inline char read() {
	static const int IN_LEN = 1000000;
	static char buf[IN_LEN], *s, *t;
	return (s==t?t=(s=buf)+fread(buf,1,IN_LEN,stdin),(s==t?-1:*s++):*s++);
}
template<class T>
inline void read(T &x) {
	static bool iosig;
	static char c;
	for (iosig=false, c=read(); !isdigit(c); c=read()) {
		if (c == '-') iosig=true;
		if (c == -1) return;
	}
	for (x=0; isdigit(c); c=read()) x=((x+(x<<2))<<1)+(c^'0');
	if (iosig) x=-x;
}
const int OUT_LEN = 1<<21;
char obuf[OUT_LEN], *ooh=obuf;
inline void print(char c) {
	if (ooh==obuf+OUT_LEN) fwrite(obuf, 1, OUT_LEN, stdout), ooh=obuf;
	*ooh++=c;
}
inline void flush() { fwrite(obuf, 1, ooh - obuf, stdout); }

const int N = 1<<21, M = 22;
int n, cnt[N];
ull a[N], b[N];
int main() {
	read(n);
	for(int i=1; i<1<<n; ++i) cnt[i]=cnt[i^(i&-i)]+2;
	char x;
	while(isspace(x=read()));
	for(int i=0; i<1<<n; ++i) a[i]=(ull)(x-'0')<<cnt[i], x=read();
	while(isspace(x=read()));
	for(int i=0; i<1<<n; ++i) b[i]=(ull)(x-'0')<<cnt[i], x=read();

	for(int i=0; i<n; ++i) for(int j=0; j<1<<n; ++j) if(j>>i&1)
		a[j]+=a[j^(1<<i)], b[j]+=b[j^(1<<i)];
	for(int i=0; i<1<<n; ++i) a[i]*=b[i];
	for(int i=0; i<n; ++i) for(int j=0; j<1<<n; ++j) if(j>>i&1) a[j]-=a[j^(1<<i)];
	for(int i=0; i<1<<n; ++i) print((char)('0'+(a[i]>>cnt[i]&3)));
	return flush(), 0;
}