dp of dp，又称 dp 套 dp。大致就是用一个 DP 的结果作为另一个 DP 的状态进行转移。

回顾一下正常人类怎么求 LCS。
设 $f_{i,j}$ 表示 $s$ 前 $i$ 个和 $t$ 前 $j$ 个匹配的 LCS 长度。

$$f_{i,j} = \left\{\begin{matrix} f_{i-1,j-1} +1 & (s_i=t_j)\\ \max\{f_{i-1,j},f_{i,j-1}\} & (s_i\ne t_j) \end{matrix}\right.$$

然后注意到本题的神秘数据范围：$|S| \leq 15$，似乎要往状压一类的东西上想？
于是我们把 $f_i$ 看成一个整体，但是 $f_i$ 这玩意儿状压不了半点。
然而可以发现这玩意儿的差分数组每一位一定是 $0$ 或 $1$，因此差分数组可以状压为一个 $15$ 位二进制数。

再考虑这题怎么做，设 $dp_{i,S}$ 表示填了 $t$ 串的前 $i$ 位，与 $s$ 串的 LCS 差分数组状态为 $S$ 的方案数（注意大小写有区别，小写是串大写是二进制数）。
设 $g_{S,k}=T$ 表示在 LCS 差分数组为 $S$ 的时候。在 $t$ 串末尾加上 $k$ 会让 LCS 差分数组转移为 $T$。
那么转移方程就是 $dp_{i,S} \rightarrow dp_{i+1,g_{S,k}}$。

#include <bits/stdc++.h>
using namespace std;
const int N = 1015, M = 20, V = (1 << 15) + 15, mod = 1e9 + 7;
const char ch[] = {'A', 'C', 'G', 'T'};
int Tid, n, m;
int pre[M], f[M];
char s[M];
int g[V][5], dp[N][V];
int ans[M];

int popcnt(int S) {
    int res = 0;
    while (S) res += (S & 1), S >>= 1;
    return res;
}

int main() {
    scanf("%d", &Tid);
    while (Tid--) {
        scanf("\n %s %d", s + 1, &m);
        n = strlen(s + 1);
        for (int i = 0; i < (1 << n); i++)
            for (int j = 0; j < 4; j++) g[i][j] = 0;
        for (int i = 1; i <= m; i++)
            for (int S = 0; S < (1 << n); S++) dp[i][S] = 0;
        for (int i = 0; i <= n; i++) ans[i] = 0;

        for (int S = 0; S < (1 << n); S++) {
            for (int i = 1; i <= n; i++) pre[i] = f[i] = 0;
            for (int i = 1; i <= n; i++) {  //差分数组转前缀和，即 lcs[i-1] 数组
                pre[i] = pre[i - 1];
                if (S & (1 << i - 1)) pre[i]++;
            }
            for (int k = 0; k < 4; k++) {
                for (int i = 1; i <= n; i++) {  //pre -> f[i-1]   f -> f[i]
                    if (s[i] == ch[k]) f[i] = pre[i - 1] + 1; //lcs[i,j]=lcs[i-1,j-1]+1;  (s[i]==t[j])
                    else f[i] = max(f[i - 1], pre[i]);    //lcs[i,j]=max(lcs[i-1,j],lcs[i,j-1]);
                }
                int T = 0;
                for (int i = 1; i <= n; i++)
                    if (f[i] - f[i - 1]) T |= (1 << i - 1);
                g[S][k] = T;
            }
        }
        dp[0][0] = 1;
        for (int i = 0; i < m; i++)
            for (int S = 0; S < (1 << n); S++)
                for (int k = 0; k < 4; k++)
                    (dp[i + 1][g[S][k]] += dp[i][S]) %= mod;
        for (int S = 0; S < (1 << n); S++) (ans[popcnt(S)] += dp[m][S]) %= mod;
        for (int i = 0; i <= n; i++) printf("%d\n", ans[i]);
    }
    return 0;
}