一只羊，两只羊，四只羊？
推式子
CF578D LCS Again
啥都不看答案就是 $n^2(m-1)$，即两个串随便选位置跳过，可以每个字符来考虑。
考虑重复情况，一个容易的就是连续段。即 $s$ 中存在存在长度为 $l$ 的相同字符，那么显然只能贡献一次，否则最后生成的必然会重复。这些连续段的贡献就是 $n\cdot(m-1)$。
还有一种，就是对于下面的串
$$\texttt{…a{\color{red}b}…}\\texttt{…{\color{red}b}a…}$$
以及
$$\texttt{…{\color{red}a}b…}\\texttt{…b{\color{red}a}…}$$
会重复统计。把所有这样二元的循环串算出来删掉重复贡献，假设当前二元循环串长度为 $k$，每枚举一位就删一次 $k-1$，实际实现时统计的 $k$ 会少 $2$，因此写的是 $-(k+1)$。
代码实现中 $ans$ 初值为 $1$，这是在处理第二个重复时多算了一个。
这题也可以从 LIS 的转移方程出发，发现有 $\mathcal O(n)$ 个状态。然后 dp of dp 做这道题。
P3228 [HNOI2013] 数列
若 $0<a_{i+1}-a_i\le m$，且 $a_k\le N$。给定 $k,m,N$，满足 $m\times (k-1)<N$，求 $a_i$ 的方案数。
$m,k\le 10^9$，$N\le 10^{18}$
设 $d_i=a_i-a_{i-1}\quad (i>1)$。
$m\times (k-1)<N$ 是个很强的条件，意味着任意一组合法 $d_i$ 都有解。答案即为：
$$ \begin{aligned} \sum\limits_{d_2,d_3,\cdots,d_k\in[1,m]}N-\sum\limits_{i=2}^kd_i&=m^{k-1}\cdot N-\sum\limits_{d}\sum\limits_{i}d_i\ &=m^{k-1}\cdot N-m^{k-1}\cdot\dfrac{(m+1)(k-1)}2 \end{aligned} $$
后半部分的推导，根据对称性，用均值乘以数量即可。
但是 $p$ 不一定质数，所以你拆个 $m$ 下来就可以了。
计数 dp
P3244 [HNOI2015] 落忆枫音
给出 DAG，其中只有 $1$ 没有入度。给出加边 $(x,y)$（可能形成环），求以 $1$ 为根的外向树个数。
如果是 DAG 咋做？考虑每个点选哪个作为父亲，数学归纳这是对的，方案为 $\prod\limits_{i=2}^n d_i$，其中 $d_i$ 表示 $i$ 的入度。
加入了环咋办？考虑减掉有环的方案，即 $\dfrac{\prod\limits_{i=2}^n d_i}{\prod\limits_{j\in S} d_j}$。但是一条边可能会形成多个环，咋办？dp 一下就好了。
ABC227E Swap
注意到有用的 $k$ 在 $\mathcal O(n^2)$，因此考虑直接 dp：
$f_{i,j,k,p}$ 表示填了 $K,E,Y$ 分别 $i,j,k$ 个，已经交换了 $p$ 次的方案数。预处理出每个字符的出现位置，然后就能做了。
ABC227F Treasure Hunting
直接维护 $k$ 个状态做不了，考虑先考虑当前的第 $k$ 大，枚举第 $k$ 大的数，假设为 $a_{u,v}$。
那么计数就是容易的，设 $f_{x,y,p}$ 表示走到 $(x,y)$ 统计了 $p$ 个不小于它的数的最小代价和，这是 $\mathcal O(n^5)$ 的 DP。
ABC259Ex Yet Another Path Counting
给出 $n\times n$ 的方阵，点有色。求起点与终点同色的路径条数。
一个显然的思路是对同一种颜色枚举点对作为起点终点，网格图上两点 $(a,b),(c,d)$ 只能向下向右走的方案数为 $\dbinom{\vert c-a\vert+\vert d-b\vert}{\vert c-a\vert}$，容易做到 $\mathcal O(n^4)$。
也有朴素 dp 的做法，即把颜色独立下来后，设 $f_{i,j}$ 表示从起点走到 $(i,j)$ 的方案数。所有颜色初值都为 $1$。转移是 $f_{i,j}=f_{i-1,j}+f_{i,j-1}$。
综合上述两种做法，对颜色进行讨论。不妨对个数不超过 $B$ 的颜色采用方案 $1$，对个数多于 $B$ 的采用方案 $2$。设方案 $1$ 中颜色出现次数为 $x_i$，那么复杂度即 $\mathcal O(\sum\limits_{i\in C}x^2)$，而 $\sum\limits_{i\in C}x_i^2\le \left(\sum\limits_{i\in C}x\right)^2$，后面是一个不超过 $n^2$ 的定值，当 $x_i$ 相等时最大，于是这方案 $1$ 的复杂度就是 $\mathcal O(n^2B)$，总复杂度就是 $\mathcal O(n^2B+\dfrac{n^4}{B})$，$B=n$ 最优。
ARC159F Good Division
手玩样例发现，一个序列 $A$ 是良好的，当且仅当 $A\bmod 2=0$ 且众数出现次数 $\le\dfrac {\vert A\vert}2$（即不存在绝对众数）。若大于显然不会消完，否则可以选择每次消当前众数，这样一定能消完。
于是容易得到 $\mathcal O(n^2)$ 做法，设 $f_i$ 表示上一个良好序列的结尾为 $i$ 的方案数，直接枚举上一个转移点 $j$ 并顺带统计众数就十分容易做到平方做法。
考虑优化，设 $cnt_{x,i}$ 表示数 $x$ 在前缀 $[1,i]$ 的出现次数，对区间 $[l,r]$ 若 $x$ 作为绝对众数，那么 $cnt_{x,r}-cnt_{x,l-1}>\dfrac{r-l+1}{2}$，化一下即 $2cnt_{x,r}-r>2cnt_{x,l-1}-(l-1)$。设 $val_{x,i}=2cnt_{x,i}-i$，那么 $x$ 作为区间 $[l,r]$ 绝对众数的充要条件就是 $val_{x,r}>val_{x,l-1}$。
进一步考虑，可以容斥来做。即先计算所有 $\sum\limits_{j<i}f_j$，再删掉非法的 $f$。考虑根号分治，把出现次数 $>B$ 的用 $val_{i,x}$ 统计，共有 $\dfrac nB$ 个，那么直接前缀和一下即可。出现次数 $\le B$ 的数能够成为绝对众数的区间长度一定不超过 $2B$，这部分直接向前暴力拓展即可。
平衡一下，令 $B=\sqrt n$，总复杂度 $\mathcal O(n\sqrt n)$。但是强力的数据构造我过不去。
于是考虑换一种做法。延续 $val_{x,r}>val_{x,l-1}$ 的想法，注意到一个 $f_{i}$ 被 $j$ 贡献当且仅当存在 $x$ 满足上述条件。注意到一个前缀至多有 $\log$ 个可以作为绝对众数的数，这是由于每多一个至少使长度拓展一倍。考虑 CDQ 分治，对于区间 $[l,r]$，先算好 $[l,mid]$ 的 dp 值，然后这段区间的绝对众数必然同时是 $[l,mid]$ 的后缀或者 $(mid,r]$ 的前缀的绝对众数。因此对于这 $\log$ 个众数跑双指针，即可优化到 $\mathcal O(n\log^2 n)$。
AGC040C Neither AB nor BA
若没有 C，那么是好做的。直接把奇数位置上的 A 赋值为 $1$，偶数位赋值为 $-1$，B 相反。那么一对数能删，必须和为 $0$。很显然和为 $0$ 才能删完，这是充要的。和为 $0$ 说明 $-1,1$ 数相等，每次删相邻的 $-1,1$ 即可。
加入 C 咋做？假设当前和为负，你就不断加 C 进行调整，所以这个 C 的值是用来调整的。调整的前提是 $\max(A,B)\le \dfrac n2$，否则加 C 再多也没用。于是发现合法的序列可以的充要条件的就是 $\max(A,B)\le \dfrac n2$，容斥一下就没了。
$$Ans=3^n-2\sum\limits_{j=\frac n2+1}\dbinom nj2^{n-j}$$
CF1810G The Maximum Prefix
设 $f_{i,j,k}$ 表示前缀 $[1,i]$ 的和等于 $j$，此时的前缀最大值为 $k$ 的概率。复杂度为 $\mathcal O(n^3)$，难以接受。
但是你从后向前求，假设 $[i+1,n]$ 的前缀最大和为 $mx$，那么考虑自然从 $[i+1,n]\to[i,n]$ 就是 $mx\gets \max(mx+a_i,0)$，于是就可以丢到一维度，设 $f_{i,j}$ 表示前缀 $[i,n]$ 的前缀和最大值为 $j$ 的概率，有
$$ \begin{cases} f_{i,\max(j+1,0)}\gets f_{i+1,j}\times p_i \ f_{i,\max(j-1,0)}\gets f_{i+1,j}\times (1-p_i) \end{cases} $$
但是有点痛苦的是，这样的做法只能做 $k=n$ 的部分，否则还是 $\mathcal O(n^3)$。继续考虑，发现对于每个 $k$，初值是 $f_{k+1,0}=1$ 。如果不看初值，只看转移系数，那么从每个 $f_{1,i}$ 转移过来就好，设 $g_{1,h_i}=h_i$，然后向后转移。答案就是 $g_{k,0}$。