又是一道神题，看题解+看代码，三个小时终于会了QAQ。

• dp套dp的经典题目。
• 什么问题是dp套dp问题？这类问题让你求解的是有多少种方案使得一个dp的最终值为一个特定值。对应到本题来说，是让你求解有多少种长度为m的字符串，与S串的\(LCS\)为\(i\)。
• 这类问题，我们一般要观察原本dp的求解过程与自身性质，把内dp尝试压成状态，递推外dp值。
• 考虑\(LCS\)的求解过程。
  \[f[i][j]=max (f[i-1][j],f[i][j-1])\]
  \[if(s[i]==t[j])~~~f[i][j]=max(f[i-1][j-1]+1)\]
• 当T串确定的时候，\(f[i][j],1<=i<=n\)，这个值是单调不减的。并且相邻两个的差值最大为1。因此，我们可以把f数组差分，压成二进制数。然后每一个状态（即二进制数）对应一个T串，假如一个新的字符假如T串，它与S的\(LCS\)匹配形成的新状态，我们是可以预处理出来的。
• 现在我们可以跑dp了。\(dp[i][j]\)表示到了第i个字符，匹配状态为\(j\)的方案数。那么\(dp[i+1][tr[j][k]]+=dp[i][j]\)，其中\(tr[j][k]\)代表\(j\)代表的串加进\(k\)字符后形成的新状态。

• okk，终于做完了。记得多组数据的时候，数组一定不要忘了memset！今天第二次因为这个挂掉了233.

  Coding

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e3+1;
const int mod=1e9+7;
const int M=1<<15;
const int maxn=15;
int n,m,t,a[maxn+2],tran[M][5],f[N+2][M+2],tf[2][17],ans[17];
char s[maxn+1];char ch[5]={'a','A','C','T','G'};
int change(char c){
    for(int i=1;i<=4;++i) if(c==ch[i]) return i;
    return 5;
}
int trans(int v,int c){
    memset(tf,0,sizeof(tf));
    for(int i=0;i<n;++i) tf[0][i+1]=(v>>i)&1;
    for(int i=1;i<=n;++i) tf[0][i]+=tf[0][i-1];
    for(int i=1;i<=n;++i){
        int tmp=0;
        tf[1][i]=max(tf[0][i],tf[1][i-1]);
        if(a[i]==c)
            tf[1][i]=max(tf[1][i],tf[0][i-1]+1);
    }
    int res=0;
    for(int i=0;i<n;++i) res+=(1<<i)*(tf[1][i+1]-tf[1][i]);
    return res;
}
int count(int v){
    int res=0;
    for(int i=0;i<maxn;++i) res+=((v>>i)&1);
    return res;
}
int main(){
    scanf("%d",&t);
    while(t--){
        memset(tran,0,sizeof(tran));
        memset(ans,0,sizeof(ans));
        memset(f,0,sizeof(f));
        scanf("%s",s+1);
        n=strlen(s+1);
        scanf("%d",&m);
        for(int i=1;i<=n;++i) a[i]=change(s[i]);
        for(int i=0;i<(1<<n);++i) for(int j=1;j<=4;++j) tran[i][j]=trans(i,j);
        f[0][0]=1;
        for(int i=1;i<=m;++i){
            for(int j=0;j<(1<<n);++j){
                for(int k=1;k<=4;++k){
                    int x=tran[j][k];
                    f[i][x]=(f[i][x]+f[i-1][j])%mod;
                }
            }
        }
        for(int i=0;i<(1<<n);++i) ans[count(i)]=(ans[count(i)]+f[m][i])%mod;
        for(int i=0;i<=n;++i) printf("%d\n",ans[i]);
    }
    return 0;
}