萌新由于太弱被卡了常。~~那一定是FMT自身常数太大了~~
_____
如果不会 FMT 可以移步谷谷的板子题或者[我的博客](https://www.orchidany.cn/2019/08/26/fmt/)
快速子集变换(FST)是在 FMT 基础上的扩展，解决的也是子集交卷积，但是限制了状态不重复，即
$$c_i=\sum_{\begin{aligned}~k &\cup j=i\\ k &\cap j= \emptyset \end{aligned}}a_kb_j$$
换个写法：
$$
c_s=\sum_{t\subseteq s}a_sb_{s-t}
$$
这东西其实也不是非要用 FMT 来做，FWT 也可以。
然后就是考虑在卷积的时候多增加一维，即 $f_{i,S}$ 表示集合 $S$ 中有 $i$ 个元素，于是发现只有当元素个数相加符合时才是对的。
于是一开始将 $f_{bct(s),s}$ 赋值为 $f_s$，其中 $bct(s)=\rm bitcount(s)$。然后对每一个 $f_i$ 分别做 FMT，之后按位乘的时候需要
$$P_{i, S}=\sum_{i=0}^{i} f_{j, S} \times g_{i-j, S}$$
输出的时候只输出 $P_{bct(s),s}$ 即可。
复杂度似乎是两个 $\log$ 的？然而并不满。推荐取模优化。
```cpp
#define MAXN 21
#define MAXM 2000010
#define Mod 1000000009
#define I inline
#define LL long long
using namespace std;
int bc[MAXM];
int N, M;
int A[MAXN][MAXM], B[MAXN][MAXM], C[MAXN][MAXM];
I int read() {
int x = 0, f = 1;
char ch = getchar();
while (ch < '0' || ch > '9') {
if (ch == '-')
f = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
x = x * 10 + ch - '0';
ch = getchar();
}
return x * f;
}
I void reduce(int &x) { x += x >> 31 & Mod; }
I void Ifmt(int *f) {
register int i, j;
for (i = 0; i < N; ++i)
for (j = 0; j <= M; ++j)
if (j >> i & 1)
reduce(f[j] -= f[j ^ 1 << i]);
}
I void fmt(int *f) {
register int i, j;
for (i = 0; i < N; ++i)
for (j = 0; j <= M; ++j)
if (j >> i & 1)
reduce(f[j] += f[j ^ 1 << i] - Mod);
}
int main() {
cin >> N;
M = (1 << N) - 1;
register int i, j, s;
for (i = 1; i <= M; ++i) bc[i] = bc[i - (i & -i)] + 1;
for (i = 0; i <= M; ++i) A[bc[i]][i] = read();
for (i = 0; i <= M; ++i) B[bc[i]][i] = read();
for (i = 0; i <= N; ++i) fmt(A[i]), fmt(B[i]);
for (i = 0; i <= N; ++i)
for (j = 0; j <= i; ++j)
for (s = 0; s <= M; ++s) (C[i][s] += 1ll * A[j][s] * B[i - j][s] % Mod) %= Mod;
for (i = 0; i <= N; ++i) Ifmt(C[i]);
for (i = 0; i <= M; ++i) printf("%d ", C[bc[i]][i]);
}
```