本文参考了 Dance of Faith 大佬的博客
我们定义集合并卷积
最暴力的时候只能 (O(4^n)) 完成，进行 一些优化 可以在 (O(3^n)) 内完成，当然我们可以在 (O(n 2^n)) 利用 (FMT) 或者 (FWT) 内快速处理。
(FMT) 原理更好理解，就介绍此种方式。
具体来说，类似与 (FFT) 我们把 (f,g) 求点值，然后点值相乘后再插值变化回去。因为要快速实现这个过程，我们可以考虑利用 快速莫比乌斯变换 和 快速莫比乌斯反演 实现。
定义
定义 (f) 的莫比乌斯变换 (hat{f}) ，满足 (hat{f_S} = sum_{T subseteq S} f_T) 。（也就是 (hat{f}) 是原来函数 (f) 的子集和）
定义 (hat{f}) 的莫比乌斯反演 (f) ，利用容斥原理可以得到 (f_S = sum_{T subseteq S} (-1)^{|S| - |T|} f_{T}) 。
考虑为什么这个形式满足集合并卷积。
[h_{S} = sum_{L subseteq S}^{} sum_{R subseteq S}^{} [L cup R = S] f_{L} * g_{R} ]左右同时做莫比乌斯变换。
[egin{aligned} hat{h_{S}} &= sum_{T subseteq S} sum_{L subseteq T} sum_{R subseteq T} [L cup R = T] f_{L} * g_{R}\ &= sum_{L subseteq S} sum_{R subseteq S} [L cup R subseteq S] f_{L} * g_{R} end{aligned} ]由于 ([L cup R subseteq S] = [L subseteq S][R subseteq S]) ，也就有
[egin{aligned} hat{h_{S}} &= sum_{L subseteq S} sum_{R subseteq S} f_{L} * g_{R}\ &= (sum_{L subseteq S}f_L)(sum_{L subseteq S}g_R)\ &=hat{f_L} * hat{g_R} end{aligned} ]证毕。
快速变换与反演
原理讲解
上面那两个集合和我们暴力做是 (O(3^n)) 的，可以进行优化。
考虑按 集合大小 分层递推。
令 (hat{f_{S}}^{(i)}) 为 (sum_{T subseteq S} [(S - T) subseteq {0, 1, 2, ..., i}] f_{T}) ，有 (hat{f}_S^{(0)} = f_S) 。
那么对于不包含 ({i}) 的集合 (S) ，满足 (hat{f_{S}}^{(i)} = hat{f_{S}}^{(i - 1)}) ，那么它的贡献就是
这样，递推 (n) 轮后 (hat{f}^{(n)}_S) 就包含所有情况，即为所求变换。
对于莫比乌斯反演的话，同样递推，不断减掉就行了。
代码实现
void FMT(int *f, int opt) {
for (int j = 0; j < n; ++ j)
for (int i = 0; i < (1 << n); ++ i) if (i >> j & 1)
f[i] += opt * f[i ^ (1 << j)];
}
子集卷积
原理讲解
我们定义 (f) 与 (g) 的子集卷积 (f * g = h) 。
其实就是
刚刚讲的子集并卷积为何不行呢？因为有 ([L cap R = varnothing]) 的这个限制。
如何去掉这个限制呢，我们多记一维集合大小，也就是 (f_{i, S}) 表示有 (i) 个元素，集合表示为 (S) 。
显然当且仅当 (i = |S|) 时是正确的，我们先做 (FMT) 。
所以递推的时候就是 (h_{i + j, S} = sum_{i, j} f_{i, S} * g_{j, S}) ，其实是个多项式乘法。
由于前面对于 (n) 个函数进行 (FMT) 需要 (O(n^2 2^n)) 的复杂度。
这里 (FFT) 也优化不了复杂度（而且由于常数会慢很多），那么直接暴力卷积就好了。
代码实现
for (int i = 0; i <= n; ++ i) {
for (int j = 0; i + j <= n; ++ j)
for (int S = 0; S < (1 << n); ++ S)
h[i + j][S] += f[i][S] * g[j][S];
}
最后我们要求 (S) 的子集卷积的结果，直接用 (h_{ ext{bitcount(S)}, S}) (IFMT) 的。
子集逆卷积
原理讲解
我们有时候需要做子集卷积意义下的除法或者相关运算。
比如对于两个函数 (f * g = h) ，我们已知 (g, h) 要求 (f) 。
那么就是 (f = h * g^{-1}) 。其实就是要求 (g^{-1}) 在子集卷积意义下的结果。
同样我们只需要考虑 (FMT) 之后的结果。
由于对于每一位我们做的是多项式下的乘法。其实就是对于每一位求的 (g^{-1}) 就是多项式求逆后的结果。
同样对于别的运算也是多项式后的结果。
但是写那个 (O(n log n)) 的倍增多项式求逆显然十分地麻烦，可以考虑 (O(n ^ 2)) 递推。
令 (g^{-1} = t) 假设我们求出 (t_{0, 1, cdots, i - 1}) ，要求 (t_i) 。((t_0 = g_0^{-1})) 。
我们可以把 (g_i) 减去 (t) 和 (g) 前 (i - 1) 项做卷积后的第 (i) 项的值，就是所求的 (t_i) 。
这样就可以解决啦qwq
代码
inline void Inv(int *f) {
tmp[0] = fpm(f[0], Mod - 2);
for (int i = 0; i <= n; ++ i) {
inv[i] = tmp[i];
for (int j = 0; i + j <= n; ++ j)
tmp[i + j] -= inv[i] * f[j];
}
}