题面

给你一个只由\(AGCT\)组成的字符串\(S (|S| ≤ 15)\)，对于每个\(0 ≤ .. ≤ |S|\)，问

有多少个只由\(AGCT\)组成的长度为\(m(1 ≤ m ≤ 1000)\)的字符串\(T\)，使得\(LCS(T,S)=i\)？

题解

老早就听说这个叫做\(dp\ of\ dp\)的神仙了……然而一直没学……

我们先考虑\(LCS\)是怎么转移的，设\(LCS(i,j)\)表示第一个串到\(i\)，第二个串到\(j\)为止的最长公共子序列，那么转移为

\[ LCS(i,j)=\max \begin{cases} LCS(i-1,j-1)+1 &S[i]=T[j]\\ LCS(i,j-1)\\ LCS(i-1,j) \end{cases} \]

然后我们发现\(LCS(i,j)\)的值和\(LCS(i,j-1)\)的值相差最多不会超过\(1\)

那么我们把数组的第二维差分一下，再状压成一个二进制序列，然后我们就可以预处理出\(to[s][k]\)表示当前\(LCS\)状态为\(s\)，加的下一个字符为\(k\)，可以到达的\(LCS\)状态是什么

然后设\(f[i][s]\)表示当前在第\(i\)个位置，此时\(LCS\)状态为\(s\)的方案数

那么转移方程就是

\[f[i][to[s][k]]+=f[i-1][s](k=A,T,G,C)\]

边界为\(f[0][0]=1\)

//minamoto#include
    
     #define R register#define fp(i,a,b) for(R int i=(a),I=(b)+1;i
     
      I;--i)#define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v)template
      
       inline bool cmax(T&a,const T&b){return a
       
        =P?x-=P:0;}char S[19];int to[N][4],sz[N],f[2][N],ans[1005];int n,m,lim,t;void init(){    static int d[19],g[19];    fp(s,0,lim-1){        sz[s]=sz[s>>1]+(s&1);        fp(j,0,n-1)d[j+1]=d[j]+(s>>j&1);        fp(k,0,3){            fp(j,1,n){                g[j]=max(g[j-1],d[j]);                T[k]==S[j]?cmax(g[j],d[j-1]+1):0;            }            to[s][k]=0;            fp(j,0,n-1)g[j+1]-g[j]?(to[s][k]|=(1<