联考的题解还是在这里。
做题：
ARC125F 这就是 \(\deg\) 做背包。把所有 \(\deg\) 减一。现在限制是和为 \(n-2\)，每个数是自然数。
有性质：选取和为 \(y\) 的数的个数连续。设 \(L_y\) 为最少选的数，\(R_y\) 为最多。设有 \(z\) 个 \(0\)。只需证明：
\[R_x-L_x\le 2z+1 \]对于任意方案和、个数为 \(v,w\)，有 \(v-w\in [-z,z-2]\)。因为 \(v-w=\sum_{i\in S}(\deg_i-1)\)，因为我的策略是全选 \(0\) 或者不选 \(0\)。这就证明了命题成立。
经典结论最多有 \(\sqrt n\) 个 \(\deg\)。多重背包直接二进制拆分即可 \(O(n\sqrt n\log n)\)。
P5206
\(op=0\) 直接做。
\(op=1\) 就是核心。我们不希望包含 \(f(E_1\cap E_2)\)，而最好是 \(\sum _{T\in E_1\cap E_2}f(T)\)。这里的想法是应用子集反演（和下面反着来还会带 \((-1)^{|E_1\cap E_2|}\)。。）：
设
\[f(S)=\sum_{T\subset S}g(T) \]则
\[f(S)=\sum_{T\subset S}g(T)=\sum_{T\subset S} \sum_{P\subset S}(-1)^{|T|+|P|}f(P) \]这样比较好的是甚至不带任何直接和 \(S\) 相关的项。
然后推推狮子（运用 CF156D 结论）得到最终方案是
\[\sum_{S\subset E_1}C^{|S|}\prod a_i^2 \]\(a_i\) 是割掉 \(S\) 的连通块大小，另一个经典技巧（唯一参加的一场 ARC 的 C）是 \(\prod a_i\) 变为在 \(|S|\) 个第 \(i\) 个大小是 \(a_i\) 的集合里选数。这样直接 dp 即可做到 \(O(n)\)。
\(op=2\) 只需把枚举过程变为 GF 的 exp 即可。
CF1439B 首先把 \(\deg<k-1\) 的删掉。然后暴力拉出 \(\deg =k-1\) 的判断团。接下来没删完就是答案（第二类）。注意到团的 \(k=O(\sqrt m)\)，所以复杂度是 \(O(m\sqrt m\log m)\)。
CF645F 直接莫反即可。
CF653G 分开考虑质数，就变成了取中位数问题；直接计数。
标签：总结,subset,直接,10.7,sum,cap,10.13,op,deg From： https://www.cnblogs.com/british-union/p/18464361