Educational Codeforces Round 184
D - Removal of a Sequence
之前做过 2024 昆明的题，就很套路了。
考虑时光倒流，已经做完 \(x\) 次操作后第 \(k\) 个数就是 \(k\) ，倒流一次操作，求出 \(k\) 变哪里去。
每次操作会在 \(k\) 前面插入 \(\lfloor\frac{k-1}{y-1}\rfloor\) 个数，因此有：
做 \(x\) 次就能过 D1，考虑右边的值单调上升，值域不会太大，最多 \(\sqrt{10^{12}}\) 级别，因此可以枚举值域，每次求出在往后多少次操作时右式都是同一个值，快速递推就可以，复杂度 \(O(\sqrt{V})\) 。
E - Points Selection
首先，最后最多留下 \(4\) 个点，用 \(4\) 个点一定能构造一个矩形。
那直接 dp，考虑周长关于 \(\max(x)-\min(x)+\max(y)-\min(y)\) ，设 \(f_{s\in\{0,1,2,3\}}\) 表示 \(x,y\) 的最大最小值已经确定下的最大价值，事实上偏序关系 \(\min(x)\leq \max(x)\) 自动满足，因为取反后相减是个负数，一定更劣。
F - Subsequence Problem
把 \(k\) 个序列拼成 \(k\) 个集合序列（在单个序列内不考虑顺序，只考虑不同序列间的顺序），那么合法序列满足，对于 \(1\cdots |s|\) ，\(s_i\) 在序列中第一次出先位置单调上升。
可以写一个朴素的 dp：\(f_{i,j}\) 表示当前填了 \(i\) 位，已经匹配了 \(s_{1,2,\cdots j}\) 后的方案数。转移上，可以从 \(f_{i-1,j}\) 和 \(f_{i-1,j-1}\) 转移来，前者系数是介于 \([m-5,m]\) 之间的数，根据当前所在序列已经填了多少个数（我们要求当前序列后面的数都不能出线），后者系数是 \(1\) ，我们暂时不考虑集合内数的顺序，最后乘上 \(\prod l_i!\) 就可以。
考虑加速这个转移，我们发现，从 \(f_{i-1,j-1}\) 的转移必然执行 \(\sum l_i\) 次，且在相邻两个 \(j\) 的转移间，从 \(f_{i-1,j}\) 的转移系数一致，且这个系数最多有 \(6\) 个取值，我们设这些位置为 "空位"，特别的，开头和结尾也是空位。
我们可以求出每个空位间的系数是多少，并设 \(e_i\) 表示系数为 \(i\) 的转移空位有多少。
考虑一次转移就是填了一个数，除掉必要的系数为 \(1\) 的转移外，还剩下 \(n-\sum l\) 个数字，那我们需要考虑这些数字中有几个是系数为 \(i\) 的，以及对应的顺序。
考虑系数为 \(i\) 的数我们填 \(x_i\) 个，那它的可行位置为 \(\binom{x_i+e_i-1}{e_i-1}\) 是个隔板法，填的数有 \((m-i)^{x_i}\) 的方案，我们满足 \(\sum x_i=n-\sum l_i\) 。
于是上式子直接对每个 \(i\) 都做一个关于 \(x_i\) 的多项式，乘积起来找到 \(n-\sum l_i\) 的系数就可以。