题目概述

给出长度为 $m$ 的基因串 $S$ ，对于每个 $i$ 求有多少个长度为 $n$ 的基因串 $T$ 使得 $LCS(S,T)=i$ 。

解题报告

DP套DP好像是丽洁姐取的名字……是这样的一类问题：通过一个外层的DP来计算使得另一个DP方程(子DP)最终结果为特定值的输入数。

就是说把子DP的结果作为外层DP的状态，比如这题，如果已知 $T$ 那么可以用DP $g_{i,j}$ 求出 $LCS(S[1,i],T[1,j])$ ，再定义 $f_{i,g}$ 表示 $T$ 的前 $i$ 个字符转移到了 $g$ 这一个状态的方案数。

但是这样复杂度爆炸了，我们观察一下发现只需要留下 $g$ 的第 $i$ 行就可以转移，不过即使这样复杂度还是爆炸……

这时候需要用到 $LCS$ 的性质：$g$ 的第 $i$ 行递增且相邻两个数 $g_{i,j-1},g_{i,j}$ 至多相差 $1$ ，也就是说差分一下就只剩下 $2^m$ 个状态了。

为了快速转移，我们可以预处理 $son_{s,j}$ 表示 $s$ 这个状态加上 $j$ 这个字符到达的状态，然后做外层DP的时候就只需要枚举加上的字符。复杂度 $O(2^mm+2^mn)$ 。

示例程序

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxm=15,maxs=1<<maxm,maxn=1000,MOD=1e9+7;const char op[4]={'A','C','G','T'};

int te,n,m;char a[maxm+5];int cnt[maxs],son[maxs][4],f[maxn+5][maxs],ans[maxm+5];

inline void Make(){
    static int f[maxm+5],g[maxm+5];
    for (int s=0;s<(1<<m);s++){
        cnt[s]=cnt[s>>1]+(s&1);
        for (int i=1;i<=m;i++) g[i]=g[i-1]+(s>>i-1&1);
        for (int j=0;j<4;j++){
            for (int i=1;i<=m;i++) op[j]==a[i]?f[i]=g[i-1]+1:f[i]=max(f[i-1],g[i]);
            int t=0;for (int i=1;i<=m;i++) if (f[i]>f[i-1]) t|=1<<i-1;son[s][j]=t;
        }
    }
}
#define ADD(x,y) (((x)+(y))%MOD)
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    for (scanf("%d",&te);te;te--){
        scanf("%s",a+1);m=strlen(a+1);scanf("%d",&n);Make();f[0][0]=1;
        for (int i=1;i<=n;i++){
            for (int s=0;s<(1<<m);s++) f[i][s]=0;
            for (int s=0,F;s<(1<<m);s++)
                if (F=f[i-1][s])
                    for (int j=0;j<4;j++)
                        f[i][son[s][j]]=ADD(f[i][son[s][j]],F);
        }for (int i=0;i<=m;i++) ans[i]=0;
        for (int s=0;s<(1<<m);s++) ans[cnt[s]]=ADD(ans[cnt[s]],f[n][s]);
        for (int i=0;i<=m;i++) printf("%d\n",ans[i]);
    }
    return 0;
}