$介绍$

$\textrm{dp of dp}$，又名 $\textrm{dp套dp}$，指的是在一个普通的 dp 的基础上，将 dp 的答案作为状态。

例如普通 dp 数组为 $f_i$，那么外层 dp 数组为 $g_{i,f_i}$，当然有时并不能直接用这个状态作为外层 dp。

$\textrm{例题 I}$

原题链接

给定 $n$ 和一个由 $N,O,I$ 组成，不包含子串 NOI 的字符串 $S$。

分别求有多少个只由 $N,O,I$ 三个字符组成的长度为 $n$ 的字符串使得与 $S$ 的最长公共子序列为 $len(0\leq len\leq |S|)$，并且不包含子串 NOI。

$n\leq 10^3, |S|\leq 15$。

$思路$

我们先列出求两个串 $lcs$ 的状态转移方程

$$lcs_{i,j} \left\{\begin{matrix} lcs_{i-1,j-1} +1 & (A_i=B_j)\\ \max\{lcs_{i-1,j},lcs_{i,j-1}\} & (A_i\ne B_j) \end{matrix}\right.$$

忽略不包含子串 NOI 的条件。

发现 $lca_i$ 可以用 $lcs_{i-1}$ 求得，然后设 $f_{i,g}$ 表示长度为 $i$ 的字符串中，$lca_i$ 数组为 $g$ 的字符串个数。

$f_{i+1,g’} := f_{i+1,g’}+f_{i,g}$

其中 $g’$ 为 $g$ 递推求得。

但这样状态数爆炸，发现 $lcs_{i,j}-lcs_{i,j-1} \in \{0,1\}$ ，于是 $lcs_i$ 可以用长度为 $|S|$ 的二进制数表示。

最总状态数为 $O(n2^{|S|})$，复杂度 $O(n2^{|S|}|S|)$。

最后考虑一下如何处理不包含字串 NOI，我们多设一维表示最后几个与 NOI 的匹配程度，然后和 $g$ 数组一样一起转椅即可。

$代码$

#include <bits/stdc++.h>
using namespace std;

const int N = 1010, MOD = 1e9 + 7;
int f[2][1 << 15][3], tmp[20], tmp2[20], ans[20];
char s[20], s2[3] = {'N', 'O', 'I'};

void add(int &x, int y) {
    x = (x + y) % MOD;
}

int main() {
    int n, k;
    scanf("%d%d%s", &n, &k, s + 1);
    f[0][0][0] = 1;
    for (int i = 0; i < n; i ++ ) {
        for (int j = 0; j < (1 << k); j ++ )
            for (int p = 0; p < 3; p ++ )
                f[(i + 1) & 1][j][p] = 0;
        for (int j = 0; j < (1 << k); j ++ ) {
            for (int p = 0; p < 3; p ++ ) {
                if (!f[i & 1][j][p]) continue;
                for (int ch = 0; ch < 3; ch ++ ) {
                    for (int o = 1; o <= k; o ++ ) {
                        tmp[o] = tmp[o - 1] + (j >> (o - 1) & 1);
                    }
                    for (int o = 1; o <= k; o ++ ) {
                        tmp2[o] = max(tmp2[o - 1], tmp[o]);
                        if (s2[ch] == s[o]) tmp2[o] = tmp[o - 1] + 1;
                    }
                    for (int o = k; o >= 1; o -- ) tmp2[o] -= tmp2[o - 1];
                    int to = 0, pp = (ch == p) ? p + 1 : ((ch == 0) ? 1 : 0);
                    for (int o = 1; o <= k; o ++ ) if (tmp2[o]) to += 1 << o - 1;
                    if (pp != 3) add(f[(i + 1) & 1][to][pp], f[i & 1][j][p]);
                }
            }
        }
    }
    for (int j = 0; j < (1 << k); j ++ ) {
        int l = 0;
        for (int o = 0; o < k; o ++ )
            if (j >> o & 1)
                l ++ ;
        add(ans[l], ((long long)f[n & 1][j][0] + f[n & 1][j][1] + f[n & 1][j][2]) % MOD);
    }
    for (int o = 0; o <= k; o ++ ) printf("%d\n", ans[o]);
    return 0;
}

$\textrm{例题 II}$

原题链接

给定 $n(1\leq n\leq 50)$ 个点，每个点有黑白两种颜色（如果没有颜色，那么你可以把它任意涂成黑色或白色），同时你可以在这个图上任意加入一些边（当然不能加入重边或自环），要求：加入的边必须从编号小的点指向编号大的点

我们称一条好的路径为经过的点为黑白相间的路径，如果一个图好的路径的总数 $\bmod 2=p$，那么我们称这个图为好的图，现在给定你 $n$ 个点的情况，求这 $n$ 个点能组成的好的图的个数，答案对 $10^9+7$ 取模。

很明显需要 $\textrm{dp of dp}$，考虑到原图中无边，所以顺序dp。

首先考虑在图固定，点颜色固定的情况下，我们设 $dp_i$ 表示在 $i$ 处结尾的黑白相间的路径个数，然后随便 dp 即可。

设 $f_{i,…}$ 表示对于前 $i$ 个点涂色并连边的方案，使得满足某些要求的数量。

一开始想到加入 $dp$ 数组，但这显然不行。于是注意到我们只关心 $\bmod 2$ 意义下的路径数，所以 $\forall i,dp_i\in \{0,1\}$。

但是这样还是不行，我们对点分类，$w_0$ 表示颜色为白且 $dp_j$ 为 $0$ 的 $j$，其余同理，我们得到四类 $w_0,w_1,b_0,b_1$，发现我们并不需要知道哪些位置属于 $w_0$，而更关心 $w_0$ 的数量，于是列出状态 $f_{i,w0,w1,b0}$ 表示四类数分别为 $w0,w1,b0,i-w0-w1-b0$ 的方案数。

状态数根据插板法为 $O(n^4)$。

转移式如下

void update(int x, int w0, int w1, int b0, int b1) {
    if (col[x + 1] == 0) { //black
        if (w1) add(f[x + 1][w0][w1][b0 + 1], 1ll * qpow(2, x - 1, MOD) * f[x][w0][w1][b0] % MOD);
        add(f[x + 1][w0][w1][b0], 1ll * qpow(2, w1 ? x - 1 : x, MOD) * f[x][w0][w1][b0] % MOD);
    } else { //white
        if (b1) add(f[x + 1][w0 + 1][w1][b0], 1ll * qpow(2, x - 1, MOD) * f[x][w0][w1][b0] % MOD);
        add(f[x + 1][w0][w1 + 1][b0], 1ll * qpow(2, b1 ? x - 1 : x, MOD) * f[x][w0][w1][b0] % MOD);
    }
}

若当前点为黑点，此点的 $dp_i$ 只与 $w1$ 有关，因此现乘以 $2^{n-w1}$，然后若当前点为 $b_0$，那么需要从 $w1$ 个数中选出偶数个，发现奇偶性可以有最后一个控制，所以奇数偶数都为 $2^{w1-1}$，总共就乘上 $2^{n-1}$，其余同理。

时间复杂度 $O(n^4)$。

record