0%

「Codeforces 1034E」Little C Loves 3 III

Codeforces 1034 E

题意

给你两个 \(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}\),进位是不会对最低位产生影响的

所以直接+*就好了


代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#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;
}