——《碎镜》
（不知道怎么标作者，放个链接吧）
496 ARC143F Counting Subsets
注意到在背包的过程中，第一个产生 \(2\) 的数很特殊，假设此时左右侧均有 \(k\) 个 \(1\)。归纳可证，背包左右侧 \(1\) 个数恒为 \(k\)，且转移形如“将中间部分复制一遍，并在两份中间插入长度 \([a,2a]\) 的段”。
问题对大于 \(n\) 的数并没有限制，我们可以在最后形成的方案基础上，任选一个 \(1\) 加入集合，因此我们需统计所有方案最后一个 \(2\) 与 \(n\) 距离之和。
不会 dp，放弃了。
啥时候回来看看：https://www.cnblogs.com/leukocyte/p/16500383.html
497 ARC122F Domination
不妨先考虑 \(k=1\)。
首先删去被二维偏序的红点，那么所有红点形态应 \(x\) 递减 \(y\) 递增。
合法方案肯定是每个蓝色石子覆盖一个区间，区间并为全集。不妨考虑蓝色石子 \(i\) 覆盖 \([l,r]\) 的代价：\(\max(ry_l-by_i,0)+\max(rx_r-bx_i,0)\)，两维是相对独立的，于是考虑建图来描述 \((0,ry_l)\rightarrow (0,by_i)\rightarrow (bx_i,0)\rightarrow(rx_r,0)\rightarrow\cdots\) 这一过程：
- 建立 \((x,0)\rightarrow(x+1,0),(0,y+1)\rightarrow(0,y)\)，边权为 \(1\)，表示造成贡献；
- 建立 \((x+1,0)\rightarrow(x,0),(0,y)\rightarrow(0,y+1)\)，边权为 \(0\)，表示被 \(0\) chkmax 的路径。
- 建立 \((0,by_i)\rightarrow(bx_i,0)\)，边权为 \(0\)，表示使用该蓝色石子；
- 建立 \((rx_i,0\rightarrow(0,ry_{i+1})\)，边权为 \(0\)，表示拼接区间。
答案即从 \((0,ry_1)\) 到 \((rx_n,0)\) 的最短路。
接下来考虑 \(k\) 更大的情况，我们有结论——任意合法方案都能拆成 \(k\) 个独立的 \(k=1\) 方案，最短路变为费用流即可（记得限定蓝色石子只能用一次）。
498 ARC118F Growth Rate
从后往前 dp，记 \(f_{i,j}\) 表示确定 \(X_i=j,X_{i+1},\cdots,X_n\) 的方案数，转移是后缀和形式。
归纳可证 \(f_i\) 是关于 \(j\) 的 \(n-i+1\) 次多项式，于是可以考虑插值，仅保存前 \(n-i+1\) 项的系数，转移时暴力线性插值，这样就能做到 \(O(n^3)\)。
根据经典性质只有 \(\log V\) 个非一 \(A_i\)，对于 \(A_i=1\) 容易处理，复杂度 \(O(n^2\log V)\)。
499 loj#6363. 「地底蔷薇」
先解决一个子问题：P5827 点双连通图计数。
记有根连通无向图的 EGF 为 \(C(x)\)，有根点双的 EGF 为 \(F(x)\)，将根所在的点双去除可以得到：
其中 \(D(x)\) 为 \(C(x)\) 复合逆，这种形式提示我们使用扩展拉格朗日反演，令 \(H(x)=\frac{D(x)}{x}\)：
可以 \(O(n\log n)\) 求 \([x^n]\) 系数。
回到原题，由于保证了 \(\sum_{x\in S} x\)，我们不妨求出所有合法 scc 大小对应 EGF \(P(x)\)，记有根合法无向图的 EGF 为 \(Q(x)\)，剥去根所在 scc 同样能列出式子，再次使用扩展拉格朗日反演即可。
复杂度 \(O(n\log n)\)（默认 \(n\) 与 \(\sum_{x\in S}x\) 同阶）。
500 P9480 [NOI2023] 深搜
马上更。