「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\ast 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\ast 2^n)$ 的，总复杂度 $\mathcal{O}(n^2\ast 2^n)$，无法通过此题

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

于是我们可以 $\mathcal{O}(1)$ 地完成加法和乘法，总复杂度 $\mathcal{O}(n\ast 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;
}