没做完都怪明日方舟，为什么要发这个余和令的皮肤，为什么要发那么多老陈的前瞻！
CF1842G
这我不是做过。
先把期望变成总和除以方案数的形式，于是变成了计数题。
不难发现可以将类似 \(\prod (a_i + v + \cdots)\) 的式子拆开，相当于每个多项式中选一项，对这个东西计数。
设 \(f_{i, j}\) 表示前缀 \(i\) 钦定了 \(j\) 个操作。那么转移分为当前 \(i\) 用 \(a_i\)，或之前就钦定过的 \(v\)，或者我们新钦定一个 \(v\)。
有 \(f_{i + 1, j} \leftarrow f_{i, j}(a_{i + 1} + jv)\)，\(f_{i + 1, j + 1} \leftarrow f_{i, j}(m - j)(i + 1)v\)。
然后计算答案的时候考虑我们一个 \(f_{n, i}\) 还剩下 \(n - i\) 个操作没有钦定，并且这 \(n - i\) 个操作我们没有算它的贡献。
于是答案就是 \(\frac{\sum f_{n, i}n^{m - i}}{n ^ m}\)。
Submission #346781781 - Codeforces
AGC022E
好牛的题，考虑判定转 DP。
考虑建一个 DFA 出来。如果 000 直接删掉，而 111 显然可以保留到最后，剩下的情况等价于相邻 01 对消。
那么判定一个串是否合法开一个栈即可，前半部分全是 1 后半部分全是 0，如果新加入 1 就和 0 消除，新加入超过三个 0 就消成一个。
容易发现此时只要有两个 1 就一定赢了，因为 0 也不超过两个。按照这个过程 DP 即可。
uoj748
考虑判定 \(S\) 能否到 \(T\)，一个假的贪心是直接将 \(S\) 不断地匹配到 \(T\)，但者会被 S = (((( T=()()(((( 卡掉。
考虑反悔贪心那就是对的了，于是 DP 设 \(f_{i, j, k}\) 表示 \(T\) 匹配到 \(i\)，\(S\) 匹配到 \(j\)，当前 \(T\) 中未匹配部分的前缀和为 \(k\)。如果出现 \(k < 0\) 的情况就直接反悔即可。
P9197
做过，非常典的连续段 DP。从小到大插入维护连续段即可。
AGC060C
好牛的题。
会发现题目给出一个满二叉树 \(u\) 和 \(v\) 一个在极左链上一个在极右链上，我们考虑从小到大填数，那么会发现填数的过程相当于树的拓扑序。
于是只有 \(u\) 和 \(v\) 到根的两个链是有用的，记 \(f_{i, j}\) 表示处理了左链的前 \(i\) 个结点，右链的前 \(j\) 个结点， \(P_u < P_v\) 的概率。
假设要将 \(i + 1\) 放入新的拓扑序里，那么要乘上 \(\frac{\binom{x + y}{x}}{\binom{x + y - 1}{x - 1}}\) 的概率，即 \(\frac{x}{x + y}\)。
qoj8047
很难很难。
先将 dfs 序对应到唯一的一棵树上。会发现有的东西在字数内和作为兄弟是一样的，于是我们钦定以下大小关系：父亲小于儿子，兄弟之间顺序排列，最后一个儿子大于兄弟。小于是连边的方向。
考虑将儿子到兄弟的边容斥掉，算不存在这条边的方案减去反边的方案，具体画个图就知道了。
计数考虑 DP 设 \(f_{i, j}\) 表示子树大小为 \(i\)，且兄弟连出去的部分大小为 \(j\)。转移也很复杂，自己推一推吧。
qoj1839
显然将 \(p,q\) 交换使得 \(p_i = i\) 并没有影响。
不难刻画出判定条件为不存在一对 \((i, j)\) 使得 \(i < j, q_i > q_j, s_i = 1, s_j = 0\)。
将 \((i, q_i)\) 拍进坐标系里，相当于要存在一条折线将坐标系分成两半，左上角都是 \(0\)，右下角都是 \(1\)。
结论：如果 \(q\) 确定，那么合法 \(s\) 的数量是 \(q\) 的上升子序列的数量。
那么我们直接对可能的上升子序列计数。记 \(f_{i, j, k}\) 表示前 \(i\) 个位置，当前子序列末尾为 \(j\)，当前有 \(k\) 个位置没有填数。
最终答案为：\(\sum f_{n, j, k} \cdot k!\)。
AGC020F
好诡异的套路。
先破环为链，会发现线段的长度为整数，于是我们只关心整数部分的数值和小数部分的相对大小。
那么我们可以直接 \(O(n!)\) 枚举小数部分的相对大小，相当于离散化。然后 DP 设 \(f_{i, j, s}\) 表示当前处理完了坐标 \(\leq i\) 的线段，向右延伸到了 \(j\)，用的线段状态为 \(s\)。
于是我们用神秘 \(O(n!2^n(nc)^2)\) 完成了这道题。
P4516
弱智题，设 \(f_{u, i, 0/1,0/1}\) 表示 \(u\) 子树内放了 \(i\) 个监听器，\(u\) 上是否放了监听器，\(u\) 是否被监听。
*P10064
只需要考虑叶子，令 \(S_u\) 为叶子 \(u\) 在新图上一步能到达的结点，显然 \(S\) 的并为一个连通块。于是我们将问题转化为连通块计数。
对连通块计数考虑点边容斥，每个点属于 \(S\) 的交的方案数减去边即可。
具体细节有点复杂，后面再补。
CF1476F
不算太难，考虑设 \(f_i\) 表示前 \(i\) 个灯笼覆盖到的最远前缀。
若第 \(i\) 个灯笼向右，则当 \(f_{i - 1} \geq i\) 时 \(f_i = \max(f_{i - 1}, i + p_i)\)；当 \(f_{i - 1} < i\) 时 \(f_i = f_{i - 1}\)。
若第 \(i\) 个灯笼向左，先找出最小的 \(f_t \geq i - p_i\)。那么 \(f_i \leftarrow \underset{t + 1\leq k \leq i}{\max}\{k + p_k\}\)。
第二种情况先二分 \(t\) 然后数据结构优化 \(k + p_k\) 的最大值即可。
qoj1355
设 \(f_{i, j}\) 为前 \(i\) 个音符错过了 \(j\) 个，且第 \(i\) 个音符错过的方案数。令 \(w_{l, r}\) 为 \(l \sim r\) 的所有音符都得到的贡献。
有 \(f_{i, j} = \max\{f_{i - 1, j - 1},\underset{k < i - 1}{\max}\{f_{k, j - 1} + w_{k + 1, i - 1}\} \}\)。
容易证明 \(w\) 满足四边形不等式，那么我们将 dp 视为从 \(f_{j - 1}\) 转移到 \(f_j\)，根据四边形不等式的结论：\(P_{j - 1, i - 1} \leq P_{j - 1, i}\)。
转移的时候直接分治即可优化到 \(O(n^2\log n)\)。
CF1988F
推式子基本功不够良好。
排列前缀最大值考虑一下连续段 DP，令 \(f_{i, j, k}\) 表示 \(i\) 个数的排列，前缀最大值有 \(j\) 个，有 \(k\) 个上升点，\(g_{i, j, k}\) 同理为后缀最大值。
记 \(S(n)\) 为长为 \(n\) 的排列的答案，那么枚举 \(n\) 的位置有
记
则
由于要枚举 \(n\) 于是做到 \(O(n^4)\)。原因是每个 \(n\) 都单独算一遍比较蠢。
进一步令 \(S'(n) = \frac{S(n)}{(n - 1)!}\)，\(A'(n, x) = \frac{A(n, x)}{n!}\)，\(B'(n, x) = \frac{B(n, x)}{n!}\)，\(i = p - 1, j = n - p\)，我们枚举 \((i, j)\) 贡献 \(S(i + j + 1)\)。
对每个 \(s_{i, x} = \sum_{y = 0}^j B'(j, y)c_{x + y + [i > 0]}\) 预处理即可做到 \(O(n^3)\)。
P11714
DAG 容斥模板题。以后有时间再写篇题解。
P5642
没来得及做。