定义序列 b 是好的当且仅当其可以通过若干次操作变为全 0，操作为选择 l\lt r 进行 [l,r] 区间减一。给定 n,k,m，要求长为 n 的序列中 a_i\in[0,m]。求 (k+1)^n 种可能的 a 序列中有多少是好的，对 m 取模。多组数据，n,k\le 3000,\sum n^2\le 10^7。
具体地，当出现这种位置 i 时，从 f_{i-1,j} 直接转移到 f_{i+1,t}，带上 a_i 种类数的系数 \min(j+t,m)-\max(j,t)。其余转移则需保证不存在这种位置，因此状态内需要记录 [a_i\gt a_{i-1}]。所有转移均是一段区间，只是有的与 t 有关，讨论之后将一次函数贡献到 f_{i+1},f_{i+2} 的区间内，使用差分和前缀和即可，总复杂度 O(nk)。
CF354D Transferring Pyramid
题意
给出一个金字塔，即第 i 行只在前 i 列有元素。可花费 3 的代价覆盖单个格，也可花费 \frac {x(x+1)}2+2 的代价覆盖一个高为 x 的子金字塔，求将 k 个格全覆盖的最小代价。n,k\le 10^5。
题解
显然最小代价不会超过全部单点改的 3k，于是 x 也不会超过 \sqrt k 级别。考虑对每一列 DP，设 f_{i,j} 表示考虑了前 i 列，第 i 列上最高的三角高为 j 的最小代价，第二维大小为 O(\sqrt k)。有 f_{i,j}=f_{i-1,j+1}，同时还能新开一个三角形，有 f_{i,j}\leftarrow \min{f_{i-1}}+\frac {j(j+1)}2+2。转移完后每个第 i 列上的位置再对小于它的所有 j 加上 3，这可以使用前缀和维护。总时间复杂度 O(n\sqrt k)。
P14016 ICPC 2024 Nanjing R] 拓扑
题意
给出一棵树，对所有 i 求 p_i=i 的拓扑序数量。取模，n\le 5000。
题解
由于拓扑排序是从根到底的，考虑对此设计状态，设 f_{u,i} 表示不考虑 u 子树内除 u 外的点时，p_i=u 的拓扑序数量。由于 u 子树内其他点必定在 u 之后，不会改变 u 的位置，答案为 f_{u,u}\times {n-u\choose s_u-1}\times (s_u-1)!\times \prod_{v\in son_{u}} \frac{g_v}{s_v!}，其中 s_u 表示 u 子树的大小，g_u 表示只考虑 u 子树的拓扑序数量，后面组成了多重集排列。
再考虑转移，由 u 转移到 v 时，考虑先用不在 v 子树内的点排，设 h_j 表示 p_j=u 的方案数，有 h_j=f_{u,j}\times {n-s_v-j\choose s_u-s_v-1}\times (s_u-s_v-1)!\times \prod_{t\in son_u,t\ne v}\frac{g_v}{s_v!}，同样是多重集排列。此时有 f_{v,i}=\sum_{j=1}^{i-1} h_j，将 v 插入对应位置即可，只要求 u 在其前面。求 h 只需要预处理后面一项的前后缀乘积，对 h 前缀和优化即可做到 O(n^2) 的复杂度。
本题启示我们按照过程设计 DP，从而设计出类似本题自根向下这种不常见的状态。
CF1608F MEX counting
题意
给出数组 b，求满足 a_{i}\in[0,n],\left| c_i-b_i \right|\le k 的序列个数，其中 c_i 为 a 数组前 i 个数的 MEX。n\le 2000,k\le 50。
题解
考虑设计状态，由于每个位置有自身的 MEX 限制，因此必定要记录 MEX，设 f_{i,j} 表示考虑了前 i 个数且 c_i=j 的方案数。再考虑如何转移，发现 MEX 可能单次增长很多，需要关注两个 MEX 之间的数，这也是上个 MEX 之后大于 MEX 的数。于是设 f_{i,j,c} 表示大于 MEX 的有 c 种值已存在的方案数，为方便转移，这里不确定具体值，而是只确定有 c 种。