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\)，就可以知道剩下的编号，也就可以算出来和了。
综上，我们只需要考虑求出：
\\]
首先尝试把 \(\sum\sum\) 处的 \((i, j)\) 限制给去掉，这里相当于是枚举 \(i < j\) 的有序对，只需要先算出任意的 \((i, j)\) 对，去掉 \((i, i)\) 贡献，最后 \(/ 2\) 就可以得到真实值。
于是记 \(c_s = \sum\limits_{i = 1}^m \)，只需要考虑求出：
\\]
这个形式长的就很像子集卷积，尝试对比一下子集卷积的形式：
\\]
几乎是一样的，所以尝试套用子集卷积的方法：
\[\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)^2 \]
时间复杂度 \(\mathcal{O}(2^n n^2)\)。
#include using ll = long long;constexpr int N = 20;constexpr int M = 5e5 + 10;int n, m;int lk, a, mask0;ll f[1 热心回复！
页:
[1]