目录
CF 1758 E（图论，连通块）
CF 1761 D（dp，组合数学）
CF 1761 E（图论，构造）
CF 1748 D（位运算，构造）
CF 1774 E（结论，树形 dp）
CF 1774 F2（结论，性质，数据结构）
CF 1762 F（性质，结论，dp，线段树）
CF 1749 F（树上差分，树状数组）
CF 1749 E（01BFS，转化）
CF 1743 E（dp 状态设计）
CF 1767 C（dp 状态设计）
luogu P8906（图论，分层图，分类讨论）
luogu P8907（转化，set 启发式合并）
CF 1740 F（结论，转化，计数 dp）
CF 1750 D（gcd，分解质因数，容斥）
CF 1750 E（括号序列，结论）
CF 1750 F（容斥，计数 dp）
部分题解
luogu P8906（图论，分层图，分类讨论）
USACO 2022 DEC P T1
方法一：
因为是求恰好 \(k\) 步，且 \(k\) 较小，所以可以考虑建出分层图跑 SPFA。
有 \(\mathcal{O}(nk)\) 个点，\(\mathcal{O}(n^2k)\) 跳边，因此单次更新的复杂度为 \(\mathcal{O}(n^2k)\)，总复杂度就是 \(\mathcal{O}(n^4k)\)。
但是由于每次加边的特殊性，卡不满，因此可以通过。
方法二：
注意到 \(k\) 最大只有 \(8\)，如果我们折半一下，对 \(1\) 到 \(i\) 的最短路和 \(i\) 到 \(n\) 的最短路分别维护，最大的边数就只有 \(4\)。
这启示我们可以使用一种不对 \(k\) 具有普适性的做法：分类讨论。
可以做到 \(\mathcal{O}(n^3)\)。
luogu P8907（转化，set 启发式合并）
USACO 2022 DEC P T2
删除一个点之后会把这个点连向的点互相连边，假设这个点连向的点构成的集合为 \(p\)，大小为 \(k\)。
对于边 \((i,j)(i<j)\)，考虑在 \(i\) 处计算贡献。
把集合的元素按照从小到大排序后，最小的元素为 \(p_1\)，只需要把 \(p_1\) 向所有 \(p_i(i>1)\) 连边就行了，这与之前的连边方式是等价的。
于是只需要对于每个点，维护它能连向的所有比它大的点的集合，使用 set 启发式合并即可做到 \(\mathcal{O}(n\log^2 n)\)（假设 \(n\) 和 \(m\) 同阶）。
CF 1740 F（结论，转化，计数 dp）
非常妙的转化。
对满足某种条件的可重集，可以先思考如何判定一个可重集满足条件。
设数字 \(i\) 的出现次数为 \(cnt_i\)，可重集中的元素为 \(M_i\)，且强制让其大小为 \(n\)，不足的补 \(0\)。
首先，对于一个大小为 \(k\) 的集合 \(M\)，它合法，有一个必要条件：\(\sum_{i=1}^{k}M_i\leq \sum_{i=1}^{n}\min(k,cnt_i)\)。
其次，如果两个可重集的大小相等，我们肯定希望其中的元素尽量大，因为这样才最有可能不满足条件。
也就是说，我们可以把 \(M_i\) 从大到小排序，判断每个前缀 \(1,2,3\cdots k\)，是否满足 \(\sum_{i=1}^{k}M_i\leq \sum_{i=1}^{n}\min(k,cnt_i)\) 即可。
知道了这步转化之后本题就很简单了，我们直接对这样的集合 \(M\) DP。
设 \(f(i,j,k)\) 表示从大到小考虑了集合 \(M\) 的前 \(i\) 个元素，元素和为 \(j\)，其中最小的数为 \(k\) 的方案数。
注意到 \(k\leq \lfloor\frac{n}{i}\rfloor\)，那么使用前缀和优化可以做到 \(\mathcal{O}(n^2\log n)\)。
CF 1750 D（gcd，分解质因数，容斥）
一道需要注意实现技巧的题。
做法很显然，第一个位置一定填 \(a_1\)，对于后面的位置 \(i\)，能填的数为满足 \(\gcd(a_{i-1},x)=a_i\) 的所有 \(x\)。
我刚开始的做法是利用 gcd 的性质对于每种质因数分类讨论，然后容斥，复杂度为 \(\mathcal{O(n\sqrt{m})}\)，因为每次要重新分解质因数。
但是，有一个显然的性质，\(a_i | a_{i-1}\)，且 \(a_i\) 如果有解必然单调不升。
那么，就可以转化为求满足 \(\gcd(\frac{a_{i-1}}{a_i},x)=1\) 的所有的 \(x\)，假设每次分解的数为 \(t_i\)，那么满足 \(\prod t_i\leq m\)，这样总复杂度就大约是 \(\mathcal{O}(n+\sqrt{m})\)。
CF 1750 F（容斥，计数 dp）
计数题，使用之前的技巧，考虑什么样的状态合法。
首先，\(s_1=s_n=1\)。
其次，不难得出一个性质，如果最后能够全部变成 \(1\)，那么可以通过每次合并相邻的 \(1\) 的段，使得最后的结果为 \(1\)。
但是，有一个很严重的问题是，我们无法准确地描述一个合法的状态应该满足什么条件。
正难则反，考虑容斥，思考什么样的状态不合法。
一个状态不合法，它最后一定可以得到一些 \(0\) 和 \(1\) 相间的连续段，满足任意两个相邻的 \(1\) 的连续段不能合并。
另外，我们不妨钦定最左边和最右边的连续段为 \(1\)，因为如果不为 \(1\)，最后整个串肯定不能变为 \(1\)，而我们对这样的串计数是没有意义的。
考虑这样的最终状态能够得到多少不合法的初始状态。
记 \(f_i\) 表示长度为 \(i\) 的合法状态数。
那么能得到的不合法的初始状态的数量为 \(\prod f_{len_i}\)，\(len_i\) 表示第 \(i\) 个 \(1\) 的连续段的长度。
另外记 \(g_{i,j}\) 表示长度为 \(i\) 的状态，分成若干段，其中最后一段长度为 \(j\) 的方案数。
为了方便转移，钦定 \(g_{i,i}=f_i\)。
于是有转移
\[g_{i,j}=f_j\sum_{x=1}\sum_{y=1}g_{i-x-j,y}[j+y<x] \]另外，有一个等式
\[f_i+\sum_{j=1}^{i-1}g_{i,j}=2^{i-2} \]于是可以递推算出 \(f\) 和 \(g\)。
直接做是 \(\mathcal{O}(n^4)\) 的，但是仔细分析一下边界发现转移可以写成
\[g_{i,j}=f_j\sum_{x=1}^{i-j-1}\sum_{y=1}^{x-j-1}g_{i-j-x,y} \]大概是一个三角形区域的和，使用前缀和优化可以做到 \(\mathcal{O}(n^2)\)。
标签：gcd,记录,sum,容斥,CF,2022.12,mathcal,dp From： https://www.cnblogs.com/yanchengzhi/p/17015494.html