计数dp

· · 个人记录

https://codeforces.com/problemset/problem/1943/D2

首先分析充要条件，可以通过差分之类的分析，并不那么困难。

几个优化的思路：

  1. 题解写了个容斥，可能是等价的。
  2. 合法的减去违反条件的，即 dp[i][j] = sum dp[i-1][k] - dp[i-2][k] * (a[i-1] >= j + k)

https://codeforces.com/problemset/problem/1097/G

非常套路的问题，涉及到 X^k，一般会拆成下降幂，然后用组合意义。这里的系数就是斯特林数。

组合问题应该是个不太难的树形 dp，细节留给大家自己编。

https://codeforces.com/problemset/problem/1392/H

比较直接的想法是现在的状态只和 S 里有几个元素有关。然后考虑每一轮重启之前抽了几张卡，其中有几个是新卡。就能得到一个 O(n^3) 的做法。

题解是对着这个优化，但感觉比较麻烦。有一个比较 tricky 的观察是答案等于期望的轮数 * 每一轮期望的牌数，因为这两个并不独立。

轮数的计算比较简单，可以使用 min-max 容斥之类的，或者直接递推。

https://codeforces.com/problemset/problem/1988/F

首先可以按照最大值，把整个问题分成前后两部分。

考虑如何 dp，如果从前往后做，需要记录当前元素是第几大，不容易低于 O(n^4)。从小往大做，一个元素会被别的遮住，也不好做。所以从大往小做，发现可以简单递推。

然后需要合并前后的答案，直接做还是 O(n^4)。可以分步合并。

https://codeforces.com/problemset/problem/1707/D

考察每个点最后存活的时间，那么只能有一个子树还有存活的点。用 dp[u][j] 表示 u 子树所有点恰好在 j 时刻之前删完。转移考虑 u 在 i 时刻删除，或者 u 在更早删除，但有一个子树在 i 时刻删除。

最后因为每一步要求真子集，再容斥一下。

https://codeforces.com/problemset/problem/1667/E

首先要注意到，u 这个子树有 v 个儿子，这个是好算的。然后可以用类似容斥的方法算出每个点的答案，即计算这个点子树大于一半减去后面有个重心，并且通过了这个点。

式子需要用 FFT 优化。

https://codeforces.com/contest/708/problem/E

比较幽默的题。首先如果墙没倒，一定是每一层还剩一个区间，并且相邻有交。直接做加上一点前缀和就是 O(nm^2)。

然后我们发现，只需要算这个前缀和即可，根本不需要把每一项算出来。就变成了 O(nm)。

https://codeforces.com/problemset/problem/1842/H

看起来是实数的问题，比较难以分析。把所有数减去 1/2 之后就是一个，只和大小/正负相关的问题，变成一个离散的问题。

两个数相加的正负只和绝对值大的数有关，从大到小做即可。

https://codeforces.com/problemset/problem/756/E

好像是个裸的数位背包，因为 b[i] 有限制。

可以补充一下 b[i] 无限制，但是倍率之和是 bounded 版本，比如分解成 2 的 幂次 之和。

https://codeforces.com/problemset/problem/1792/F1

主要难度在于图的性质的刻画。因为不能同时红蓝连通，考虑整个图，可以被划分成两个部分然后递归构造。

这样能比较简单写出转移，但是 F2 要写半在线卷积。

https://codeforces.com/problemset/problem/506/E

比较经典的问题。因为要求多少个不同的回文串，所以从两边开始往里添加字母，贪心匹配。直接做时间复杂度为 O(n|s|^2)。几个优化的思路：

  1. 猜想（或者分析）是项数不超过 O(|s|) 的线性递推，使用 暴力 + BM 直接解决。

  2. 两边做转移的时候每段是 24 或者 25，考虑把这个过程压缩起来，直接记录多少段 24 或者 25，那么就是 O(|s|^4)，然后再分析一下 24 和 25 它们有数量关系，所以就是 O(|s|^3)。

实际上所有基于矩阵乘法的题容易被 BM overkill，所以现在这样的题比较少见。

https://codeforces.com/contest/1810/problem/G

讲过很多次了。一个比较经典的 dp 转置的问题。