构造算法和动态规划
构造算法和动态规划
在我们用DP计数的时候，经常会遇到要求统计不同结果的DP，由于统计的是结果，因此两个不相交的中间状态最终可能会导出相同的结果。这就会导致一个重复统计的问题，有些结果我们统计了多次。
这里讲一下这类问题的通用思路。我们设计一套构造型算法$f:V\rightarrow T$，我们可以将指导构造型算法的命令序列（$f$的入参）视作一个向量$v\in V$，向量的第$i$个维度的值$v_i$对应构造型算法的第$i$步操作，而$f(v)$就是构造型算法的输出了，其对应一个结果集合（注意是结果集合而不是一个结果）。对于每个可能的结果$r$，构造型算法都要能构造出来，即存在某个向量$v$，满足$r\in f(v)$，并且命令向量可以对结果做一个划分，换言之，若$v\neq u$，那么$f(v)\cap f(u)=\emptyset$。
这样的好处就是我们在根据命令向量做DP计算的时候，由于是不同的命令序列，因此可以保证得到的结果也都是不同的。我们需要的就是通过DP统计每个命令序列的结果集合大小，最后将其加总起来就可以了。
计算包含某个子串的所有串
题目1：给定一个长度为$n$的串$s$，问存在多少长度为$m$的串，满足$s$是它的子序列（即从中删除一些字符后剩下的字符能拼接成$s$）。这里$1\leq n\leq m\leq 10^6$，$s$和构造出来的串中使用的字符集大小为$c$。
这个问题就是典型的构造型DP问题。可以发现直接统计结果数很容易会重复统计。并且由于求得是子序列而不是子串，因此也不能KMP或AC自动机的数据结构来统计。
下面我们来设计一个构造型算法。对于某个结果，我们设计的构造型算法是这样的。我们构造一个长度在$n$和$m$之间的向量$v$，其中向量的每个元素都是01，且其中正好有$n$个1，且最后一个数就是$1$。我们可以这样解读构造过程，一开始我们有一个空的字符串，对于步骤$i$，记$p=1+\sum_{j=1}^{i-1}v_i$，如果$v_i$不是0，则向构造的字符串后插入一个与$s_p$不同的字符，否则向构造的字符串后面插入$s_p$。当所有命令处理完成，就向构造的字符串尾部插入任意字符，直到它的长度达到$m$。
可以发现每个结果都可以由某个命令向量构造出来，且不同命令向量的产出是没有交集的，且对于长度为$k$的命令序列恰好对应$(c-1)^{k-n}c^{m-k}$个可能的结果。以公式的形式表达，我们要统计的结果数为：
\[\sum_{k=n}^m(c-1)^{k-n}c^{m-k}{k-1 \choose n-1}\]上面的结果我们可以通过预处理组合数和指数的方式快速计算出来，时间复杂度为$O(m)$。
计算网格扩展问题
题目2：假设有一个网格矩阵，初始的时候高度为$a$，宽度为$b$，且每个单元格的颜色均为白色。之后我们重复下面操作将矩阵的高变成$c$，宽变成$d$。
- 每次操作你可以在网格矩阵的上面加上一行，或右边加上一列，新加的行列覆盖的白色单元格中需要选取一个染成黑色
要求计算有多少不同的结果。其中$1\leq a\leq c\leq 3000,1\leq b\leq d\leq 3000$。
一道atcoder的题目。
这个问题也可以用构造型DP来解决。我们考虑命令序列，我们的命令序列是一个长度恰好为$n=c+d-a-b$的01向量$v$。下面我们考虑如何通过命令向量构造结果集合：一开始的网格是$a$行$b$列的，考虑$v_i$，如果$v_i=0$，则表示向网格的右边加上一列，这里特殊判断如果$v_{i-1}=1$，则染色的为新列的最高的单元格，否则任意染色。否则如果$v_i=1$，则向上增加一行。
我们考虑将结果翻译回命令向量，假设现在我们已经翻译了一部分，且已经构造了高度为$h$，宽度为$w$的矩阵。如果第$h+1$列加入时染色的块高度$t$不超过$w$，我们就向命令向量插入一个$0$，否则我们就插入$t-h$个$1$后再插入一个$0$。同时我们容易发现从结果到命令向量的构造方式是唯一的。
接下来考虑怎么统计最终的结果。我们发现需要构造一个长度为$n$的01序列，且其中$0$出现次数为$d-b$，$1$出现的次数为$c-a$。命令向量$v$对应的结果集合大小为的计算方式为
\[\prod_{v_i=1}(b+\sum_{j=1}^i[v_j=0])\cdot \prod_{v_i=0\land v_{i-1}=0}(a+\sum_{j=1}^i[v_j=1])\]上面这些统计结果可以通过DP计算，具体做法就是记$dp(i,j,k)$表示当前构造的01向量中$0$出现了$i$次，$1$出现了$j$次，且最后一个出现的数为$k$，上面公式中的前缀乘积。具体的贡献计算非常简单，时间复杂度为$O(2(c-a)(d-b))$。