dp 方法——状态机的判定

随笔。

大多数 $\rm dp$ 都是套了一个判定方法当状态。

序列 $\rm dp$ 考虑从左往右判定的过程。

局限性：总是状态机的第 $i$ 个时刻转移到第 $i+1$ 个时刻，无法跨层转移。

所以不管什么时候我们用了状态机判定的方法，都要考虑能不能利用跨层转移优化。

P5371 [SNOI2019] 纸牌

考虑一个顺序判定方法：覆盖第一个位置的顺子不可能 $\ge 3$ ，否则可以换成三个刻子。

所以第一个位置尽可能选刻子，剩的一定是顺子，归纳地进行这个过程，我们就可以判定了。

不牛的状态是 $f_{i,c1,c2}$ 表示前一个用 $c1$ 个当顺子，前两个用 $c2$ 个当顺子， $c1,c2\le 5$ 。

但其实我们只需要知道覆盖 $i-2,i-1,i$ 的顺子个数，和 $i-1,i,i+1$ 的顺子个数，这样向后推的时候我们就知道了 $i$ 处向后有几个顺子。

$f_{i,c1,c2}$ 表示 $i-2,i-1,i$ 用了 $c1$ 个， $i,i+1,i+2$ 用了 $c2$ 个。

转移时枚举 $i+3$ 的系数即可确定这个位置的系数。

树上 $\rm dp$ 考虑在 $\rm dfs$ 中判定的过程。

状态数的分析

有些计数类 $\rm dp$ 状态数不多，可以先写一个朴素 $\rm dp$ 再观察状态有多少种取值。

LOJ#3073. 「2019 集训队互测 Day 2」序列

状态转移图

一个数组，每个元素是 $A,B,?$ ，你需要把 $?$ 填上，给定 $k$ ，你需要让尽力消除相邻相等字符后的串的长度为 $k$ ，问方案数。

$n\le 10^6$ 。

先说结论：奇数取反， $ans=|num_A-num_B|$ 。

我们可以画出状态转移图来自然地推出这个东西。

考虑栈的匹配过程， $f_{i,j}$ 的状态不难设出。

将能转移的状态排布到该状态的两边，我们能得到 $\cdots,BAB,BA,B,\varnothing,A,AB,ABA,\cdots$ 。

发现每一步不管往左还是往右，奇偶性是确定的，而 $A$ 的作用就是奇数右移、偶数左移。

从这里就可以看到与全局状态有关了。

状态数

斯特林公式： $n!\sim \frac{n^n}{e^n}\sqrt n$ 。

积分： $\sum_{i=1}^n\frac{n}{\sqrt i}\sim\int_{1}^n\frac{n}{\sqrt i}di=\mathcal O(n\sqrt n)$ 。

P4426 [HNOI/AHOI2018] 毒瘤

给定图，求独立集个数， $n\le10^5,m\le n+10$ 。

广义串并联图，但这个是 $2^{2k}$ 的，很菜。

考虑直接搞一棵生成树出来，然后对特殊点建虚树，把虚树的每条边在原图上缩掉，你发现我们现在可以对边容斥了，枚举 $S$ 集合里的边两边都选即可，复杂度 $2^k\text{poly}(k)$ 。

自动机

多数题我们写出朴素 $\rm dp$ 就获得了一个自动机，观察转移的 $\rm DAG$ 就可以提取出转移本质相同的点，优化状态数。

CF506E Mr. Kitayuta’s Gift

给定一个小写字符串 $s$ 和一个正整数 $n$ 。

要求在 $s$ 中插入恰好 $n$ 个小写字符使其回文的方案数，两个方案不同当且仅当它们得到的串不同，与插入顺序和位置无关。

$|s| \le 200$ ， $n \le 10^9$ ，答案对 $10^4 + 7$ 取模。

这其实是在构建一个点数为 $O(|s|)$ 的回文超串自动机。

首先考虑一个判定方法，正着跑子序列自动机不牛完了，回文串是一个更强的结构，最好的方式是从回文串两边往中间匹配。

状态是 $f_{i,l,r}$ 表示遍历了大小为 $i$ 的前后缀， $[l,r]$ 没有匹配上，转移：

$\begin{cases} f_{i,l+1,r-1}\gets f_{l,r},f_{l,r}\gets 25f_{l,r}&s_l=s_r \\f_{i,l+1,r}\gets f_{l,r},f_{i,l,r-1}\gets f_{l,r},f_{l,r}\gets 24f_{l,r}&s_l\ne s_r\end{cases}$

对于 $l=r$ 的点还要向垃圾节点连一条 $1$ 边，垃圾节点连 $26$ 的自环。

这个自动机有 $|s|^2$ 个点，不牛。

把自动机画出来，我们发现有些点出度是 $2$ ，有些是 $1$ 。

$1$ 的个数可以确定 $2$ 的个数，具体来说设两个分别为 $a,b$ ，那么 $a=\lceil \frac{|s|-b}2\rceil$ 。

所以只需要关心路径上 $2$ 的个数，对这个 $\rm DAG$ 跑 $\rm dp$ 就可以求出每种本质不同路径的条数。

对每种路径跑一个矩阵快速幂就是 $|s|^4$ 。

考虑构造一个自动机，见第一篇题解，这样再跑矩阵快速幂就是 $\mathcal O(|s|^3\log n)$ 了。

需要注意的是，当 $|s|+n\bmod 2=1$ 的时候，最后一步只能添加一个字符，不能匹配诸如 add 中的 dd。

所以写 $\rm DAG$ 上记忆化搜索的时候要写终点搜到起点，不要写起点到终点，这样我们可以方便地特判最后一步的 dd。

做一个容斥，第二次只保留最后一步是双字符的点路径条数，然后把垃圾点的自环去掉。