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