主要是在打 ZR 二十连测和国庆集训，可以翻博客有 ZR 笔记。
FZ国庆集训 D1 T4
U611922。
考虑这个拓展的过程显然可以用 dijkstra 做。然后每次加一个数考虑主席树，要比较大小所以不妨考虑线段树上维护哈希，并且每个点维护一下幂次，每次二分出第一个幂次不等的点，即可判断。代码魔怔难写。
FZ国庆集训 D1 T5
U611923。非常厉害的题。
先 \(O(n ^ 2)\) 求出以 \(1\) 为根的 \(f_{u, i}\) 表示以 \(u\) 为根的子树内 \(u\) 必选，一共选 \(i\) 个的答案。然后换根 \(u \to v\) 的时候再把 \(v\) 子树内和另一半的背包合并起来。但会发现这样就不是 \(O(n ^ 2)\) 的了，因为不能保证一个点对只被计算一次，所以是 \(O(n^3)\) 的。
优化一下，发现将点 \(u\) 看作多项式 \(F_u(x) = \sum f_{u, i} x^i\)。DP 的时候对于结点 \(u\) 子树内做一次，上方再做一次。子树内是好做的，记为 \(G_u(x)\) 有 \(G_u(x) = a_u \times x \times \prod_{v \in son(u)} F_v(x)\)，对于上方的贡献，分为父亲侧和兄弟侧，父亲侧已知，兄弟侧的可以用前缀乘以后缀来做。
直接 NTT 可以做到 \(O(n^2\log n)\)，按理来说能过实际过不了。
然后是经典 trick，我们考虑拉格朗日插值，会发现 \(F_u(x)\) 是不超过 \(k + 1\) 次的多项式，所以有 \(F_u(x) = \sum_{i = 0}^{n - 1} y_i \prod_{j \not = i} \frac{x - x_j}{x_i - x_j}\)。不妨将 \(x_i = i\)，这样子分母部分可以用两个阶乘表示。我们考虑对于每个值 \(x \in [0, k]\) 代入上述多项式中的 \(x\)，总复杂度为 \(O(nk)\)，这样我们就有了 \(y\)。
我们的目标是求 \(x\) 的系数和，而现在我们主要要求 \(\frac{\prod (x - j)}{x - i}\) 这个东西。对于上面的东西，考虑这相当于一个多项式乘法，我们可以直接 \(O(k^2)\) 预处理这个东西。令 \(h_i\) 为当前 \(x^i\) 的系数，新加了 \((x - t)\)，则 \(h_i \leftarrow h_{i - 1} - t h_i\)。
那么除以 \(x - i\)，可以再倒推一遍，有 \(h_n = h^{'}_{n + 1}\)，\(h_i \leftarrow h^{'}_{i + 1} + j \times h_{i + 1}\)。
于是我们做完了！
FZ国庆集训 D1 T6
U611926。套路题。
可以将互不相交转化成求最大权独立集，然后考虑怎么建图。考虑将所有可能的匹配当做点，会相交的匹配之间连边，但这样一个起点只能匹配一个终点，变成一般图就做不了了。然而我们发现对于一个点出发的所有匹配的点权可以差分表示。但这样可能出现负数的点权，会发现这些如果一个匹配距离又远，权值还小我们一定不选，所以我们只要保留权值单调的匹配即可。
由于行之间不交，列之间也不交，所以这个图显然是二分图，直接网络流求最小权点覆盖即可。
FZ国庆集训 D1 T7
U611930。DP。
显然是 dfs 序优化的树上背包。然后考虑先分析一下性质，也就是这个 \(t - h \leq k\)。第一眼看比较神秘，但会发现这个 \(-h\) 相当于有一条链可以免费选。于是我们考虑设 \(f_{i, j}\) 为 dfs 序前 \(i\) 的点取了 \(j\) 个苹果，并且 \(i\) 到根节点的路径上各免费取了一次苹果。
转移分为选和不选 \(i\) 两种。如果不选 \(i\) 则要转移到 \(r_i + 1\)，此时 \(\operatorname{lca}(i, r_i + 1) \sim i\) 这一段的免费就没了，转而成为了到 \(r_i + 1\) 的免费。
选 \(i\) 的话，显然往 \(i + 1\) 转移，如果 \(i + 1\) 在子树内那么只需要强制 \(i\) 免费一次，否则钦定当前选择的链为免费链，然后对于 \(i + 1\) 做免费链已经确定的转移。定义 \(g_{i, j}\) 为免费链已经确定的情况，那么就可以转移了。
然后由于这是多重背包，所以再单调队列优化一下就可以做到 \(O(nk)\)。
FZ国庆集训 D1 T8
U611933。
考虑有转移 \(f(i, j) \leftarrow \max(f(i - 1, j), f(i - 1, j - 1) + p_i(j^2 + aj + b))\)。
会发现两种转移之间存在分界点，然后可以用平衡树硬维护这个东西，每次二分出断点 \(t\) 然后插入 \(f_{i, t}\)，接着对 \(t\) 后面的做区间加。
但我们二分的时候需要判断 \(f(j)\) 和 \(f(j - 1)\) 的大小关系，不好直接做，于是考虑维护差分即可。
但我其实不会平衡树，这个东西感觉要变成历史遗留问题了。
FZ国庆集训 D2 T5
U614655。小清新数据结构。
考虑这个东西显然要用线段树维护单点加，然后想想一个点的答案是什么，显然是 \(\sum_{i = 1}^{x - 1} f_i(1 - p)^{x - i} + \sum_{i = x + 1}^{n} f_i(1 - p)^{i - x}\)。把 \(p^x\) 提出来就可以直接使用线段树维护答案了。
FZ国庆集训 D3 T4
U611394。
套路题，令 \(u = x + y, v = x - y\)，那么操作会使 \((u, v) \rightarrow (u - v, 2v) 或 (u + v, 2v)\)。
于是我们得到操作次数为 \(k = \log \frac{c - d}{a - b}\)，如果 \(k\) 不是整数说明无解。
然后考虑左边的怎么变，显然最后 \(c = a + b\sum_{i = 0}^{k - 1}b_i2^i, b_i \in \{-1, 1\}\)。
那么记 \(S = \sum_{i = 0}^{k - 1} b_i2^i = \frac{c - a}{b}\)。从高位往低位贪心即可，因为一个高位的影响无法使用低位操作弥补。
FZ国庆集训 D3 T6
U611527。我不会的套路。
首先经典套路将求值拆成方案数的和，即最大值为 \(k\) 拆成最大值 \(\geq i \in [1, k]\) 的方案数。
然后考虑将加一减一在图上画出来，相当于求 \((0, 0)\) 到 \((N + M, N - M)\) 的方案数。
然后考虑对于一个 \(i\)，如果 \(i \leq N-M\) 则方案数为 \(\binom{N + M}{N}\)，即随便走。
反之，直接做明显困难，考虑找一个东西与它形成双射，并且能用上面的方法计数。设我们到达了第一次到达高度 \(i\) 时的点为 \((u, i)\)，把这条路径翻转过来，即要到达 \((u, -i)\)，终点变成了 \((N + M, N - M - 2i)\)。显然每一条原路径对应一条新路径。
现在考虑新路径集合是否等于原路径。由于 \(N - M < i\)，所以 \(N - M - 2i < -i\)，于是每条新路径都存在一个能够到达 \(-i\) 的点，翻转后就对应原路径了。这样的方案数为 \(\binom{N + M}{N - i}\)。
于是答案为 \((N - M)\binom{N + M}{N} + \sum_{i = N - M + 1}^{N + M}\binom{N + M}{N - i}\)。
Edu183D
挺有意思的构造题。考虑将存在逆序对的段计数改成总段数减去单调递增段计数显然更加好做。
所以相当于要构造一堆单调递增段，然后剩下的数递减排列。考虑一个递增段的贡献是 \(\frac{L(L-1)}{2}\)，那么这相当于一个完全背包问题。可以先背包一遍找出要用的长度然后构造。构造的时候诸如 \(1,2,3,n,4,5,n-1,n - 2, n - 3, n - 4\) 就可以了。
Edu183F
首先考虑如果我们能向前走就一定会走，然后显然不能模拟，但是会发现 \(n\) 很小，所以直观上有用的状态很少。
会发现一个人目前所在格可以用 \((x, y)\) 表示，其中 \(x\) 为回合数 \(\bmod n\)，\(y\) 为当前位置 \(\bmod 2520\)。为什么是 \(2520\)，因为 \(10\) 个 \(\leq 10\) 的 \(a\) 的 \(\operatorname{lcm}\) 最大为 \(2^3 \times 3^2 \times 5 \times 7 = 2520\)。
然后考虑倍增处理出 \(f_{i, x, y}\) 表示从 \((x, y)\) 出发经过 \(2^i\) 个回合能够走的步数，然后从 \(0\) 开始一直跳到 \(m\) 就对了。
Submission #342756510 - Codeforces
CF2034F1
看起来我真的不太会计数。
考虑这个东西放到图上相当于从 \((0, 0)\) 走到 \((n, m)\)，每一步向右走得到 \(2\)，向上走的得到 \(1\)，碰到给出的关键点 \(\times 2\)。考虑将期望用权值和除以总方案数 \(\binom{n + m}{n}\) 表示，那么我们只要求权值和即可。
这个关键点显然是特殊的，考虑令 \(f_i\) 为到达关键点 \(i\) 的权值和，令 \(0\) 号点为 \((0, 0)\)，\(n + 1\) 号点为 \((n, m)\)。
则有转移 \(f_i = \sum_{j = 0}^{i - 1} 2\times g_{j, i}\times(f_j + \binom{x_j + y_j}{x_j}w(j, i))\)，\(g_{j, i}\) 是从 \(j \to i\) 不经过其它关键点的方案数。这里可以分开理解，前一半是 \(j\) 之前的贡献，后一半是 \(j \to i\) 的贡献。对于 \(j \to i\) 的贡献要 \(g_{j, i} \times \binom{x_j + y_j}{x_j}\) 才是总的方案。
然后考虑 \(g_{i, j}\) 的求法。直接容斥，有 \(g_{i, j} = \binom{x_j - x_i + y_j - y_i}{x_j - x_i} - \sum g_{i, k}\binom{x_j - x_k + y_j - y_k}{x_j - x_k}\)。
于是我们会了 \(O(k^3)\) 的做法。
CF2034F2
看起来我真的很不会计数。
跟 F1 做法没有关系，考虑经过了 \(p_0, p_1, ..., p_{k + 1}\) 的关键点。
那么值为 \(\sum_{i = 1}^{k + 1} (2(x_{p_{i}} - x_{p_{i - 1}}) + (y_{p_i} + y_{p_{i - 1}}))2^{k - i + 1} = \sum_{i = 1}^k (2^{k - i + 1} - 2^{k - i})(2x_{p_i} + y_{p_i}) + 2x_{p_{k + 1}} + y_{p_{k + 1}} = \sum_{i = 1}^k 2^{k - i}(2x_{p_i} + y_{p_i}) + 2x_{p_{k + 1}} + y_{p_{k + 1}}\)。
后面的东西可以单独处理，乘上从 \((0, 0)\) 到 \((n, m)\) 的方案数。
前面的考虑将贡献拆到每个关键点上。然后是一步很重要的转化，考虑 \(2^{k - i}\) 相当于 \([i + 1, k]\) 的点对任意选的方案数，相当于考虑将路径分为两部分，一部分是从 \((0, 0)\) 到点 \(i\)，另一部分是从 \(i + 1 \sim k\) 选出几个点必经，并且不一定恰好经过这几个点的方案数。前半部分可以直接计算，后半部分考虑 DP，有 \(f_i = \sum_{j = i + 1}^k f_j\binom{x_j - x_i + y_j - y_i}{x_j - x_i}\)。
然后就可以算答案了。
CF2153E
思路肯定是先找性质，观察题面显然应该往质数方面找性质，然后这个 \(w\) 其实就是 \(v_k\)，于是将 \(w\) 质因数分解，考虑 \(w_k(a, b)\) 和 \(w_{p_i^{c_i}}(a, b)\) 的关系。显然 \(v_k(a!) = \min{v_{p_i^{c_i}}(a!)}\)，我们钦定 \(a \leq b\)，那么 \(v_k(a!) \leq v_k(b!)\)。如果取到 \(10^{500}\) 次方那大小关系显然，否则 \(w_k(a, b) = \min{v_{p_i^{c_i}}(a!)}\)。此时会发现 \(\min{v_{p_i^{c_i}}(a!)} = \min w_{p_i^{c_i}}(a, b)\)。
于是我们得到结论 \(w_k(a, b) \geq \min w_{p_i^{c_i}}(a, b)\)，这告诉我们只有 \(k = p^c\) 时才是有用的。
然后找找 \(f_m(x, n)\) 的性质，会发现很多的 \(f\) 都是 \(0\)，设 \(p_0\) 为不超过 \(n\) 的最大质数，那么显然当 \(x < p_0\) 时 \(f_m(x, n) = 0\)。于是我们只要求很短的一段的 \(f\)，长度大约 \(150\)。
然后就可以直接做了，只需要 \(\log n\) 求出 \(p\) 的答案就可以 \(O(1)\) 推出 \(p^c\) 的答案。对于求单个 \(f\) 只需要找到所有整除 \([p_0, n]\) 中至少一个数的 \(p\) 然后不断加幂次即可。复杂度为 \(O(T\operatorname{primegap}(n)^2\log n(\log n + \log m))\)。看起来非常庞大但是完全跑不满所以能过。
ABC427E
怎么这种题还能没想出来。主要还是认为这是一个神秘状压 DP 题而不是最短路题。
虽然这个东西 DP 没法做，但是这个东西类似最短路，终态就是没有 # 的情况。然后状态考虑所有的 # 一定组成了一个矩形。
考虑记录 lx, rx, ly, ry, dx, dy 表示现在图中的 # 可以用原图中 (lx, ly) ~ (rx, ry) 的矩形偏移 dx, dy 表示，然后直接 BFS 即可。
ABC427G
是我不会做的题，只能大概复现一下思路。
这种比大小的东西往单调性方向考虑，然而原问题没有单调性，且很难用数据结构维护，所以考虑构造新的满足单调性的序列与原序列形成双射。
首先会发现，如果一个序列 \(P\) 满足 \(p_i + A \le P_{i + 1}\)，那么一定存在某个断点 \(k\) 使得 \(1 \sim k - 1\) 都在减 \(B\)，\(k \sim n\) 都在加 \(A\)。对于这种序列我们可以直接二分。所以考虑证明能够将所有原序列和一个新的有单调性的序列形成双射。
令 \(f_P(T)\) 为对于序列 \(P\)，初始值为 \(T\) 最后得到的值，则 \(f_{P + Q}(T) = f_Q(f_P(T))\)。于是我们可以很便捷的从中间进行修改。
对于序列 \((x, y)\) 我们构造 \((y - A, \max(y, x - B))\)，我们可以证明对于所有的 \(T\)，两个序列得到相同的答案。证明考虑先确定 \(\max\) 中元素的大小，然后进行分段分类讨论。
这样我们可以将两个相邻元素构造成单调的情况，就可以从尾到头不断重复这个过程将序列修成单调的形状。但直接这么合并是 \(O(|P||Q|)\) 的显然不对，考虑在序列的末尾加一个数的变化。
显然序列会变成 \(P_1, P_2, \cdots, q - kA, \max(q - (k - 1)A, P_{M - k + 1} - B),\cdots,\max(q, P_M - B)\)。
直接归并算贡献即可，为了优化复杂度将序列长度按照二进制分块就可以做到两个 \(\log\)。