CF 2070F Friends and Pizza

同学你的集合幂级数不过关。
这个题目的预期复杂度第一眼看着可能像是 \(\mathcal{O}(\operatorname{poly}(n)\ V)\)，但是细想一下这样或许要跟背包有关，而背包不好表示出两人共选的限制。
不过考虑到是选择两人，那可以尝试一些结构的合并。
注意到 \(n\le 20\)，尝试把每个人喜爱的编号看做二进制数 \(a_i\) 处理。
此时就很好表示两人 \(i, j\) 共选的集合了，就是 \(a_i\cap a_j\)。
再尝试表示出限制，记 \(P\) 是奇数块的编号集合，那么 \((i, j)\) 合法当且仅当 \(a_i\cap a_j \cap P = \varnothing\)。
并且此时就可以知道被吃掉的编号集合 \(a_i\cup a_j\)，就可以知道剩下的编号，也就可以算出来和了。
综上，我们只需要考虑求出：

\[f_s = \sum\limits_{i = 1}^m\sum\limits_{j = i + 1}^m[a_i \cup a_j = s][a_i\cap a_j \cap P = \varnothing]\]
首先尝试把 \(\sum\sum\) 处的 \((i, j)\) 限制给去掉，这里相当于是枚举 \(i < j\) 的有序对，只需要先算出任意的 \((i, j)\) 对，去掉 \((i, i)\) 贡献，最后 \(/ 2\) 就可以得到真实值。
于是记 \(c_s = \sum\limits_{i = 1}^m [a_i = s]\)，只需要考虑求出：

\[f'_s = \sum\limits_{a = 0}^{2^n}\sum\limits_{b = 0}^{2^n}[a \cup b = s]\]
这个形式长的就很像子集卷积，尝试对比一下子集卷积的形式：

\[f''_s = \sum\limits_{a = 0}^{2^n}\sum\limits_{b = 0}^{2^n} [a\cup b = s][a\cap b = \varnothing]\]
几乎是一样的，所以尝试套用子集卷积的方法：

\[\begin{align*}&a \cup b = s, a\cap b = \varnothing\\\Rightarrow &a\cup b = s, |a| + |b| = |s|\end{align*}\]
尝试转换，可以得到：

\[\begin{align*}&a\cup b = s, a\cap b\cap P = \varnothing\\\Rightarrow &a\cup b = s, (a\cap P) \cap (b\cap P) = \varnothing\\\Rightarrow &a\cup b = s, |a\cap P| + |b\cap P| = |s\cap P|\end{align*}\]
于是类似的，设计 \(x^sy^i\)，\(x\) 这一维乘法为 FWT-OR，\(y\) 这一维乘法为多项式卷积。
于是有：

\[F(x, y) = \sum\limits_{s = 0}^{2^n} c_s x^s y^{|s\cap P|}\\f'_s = [x^s y^{|s\cap P|}]F(x, y)^2 \]
时间复杂度 \(\mathcal{O}(2^n n^2)\)。
[code]#include using ll = long long;constexpr int N = 20;constexpr int M = 5e5 + 10;int n, m;int lk[M], a[N], mask0;ll f[N + 1][1