题目链接

题意

给出一个长度字符串\(T\)，其中只包含四种字符\((A,C,G,T)\),需要找一个字符串\(S\)，使得\(S\)的长度为\(m\)，问\(S\)和\(T\)的\(lcs\)为\(0,1,2...|T|\)时，分别有多少种情况。

\(|T| <= 15,m <= 1000\)

思路

考虑\(dp\)套\(dp\)(dp还能嵌套？)

先考虑已知S的情况下如何求\(lcs\)

用\(dp[i][j]\)表示\(S\)到了\(i\)位置，\(T\)到了\(j\)位置，最长公共子序列的长度。

那就有$$dp[i][j] = max(dp[i-1][j],dp[i][j-1]) \

if(S[i] == T[j]) \

dp[i][j]=max(dp[i][j],dp[i-1][j-1]+1)$$

设计状态

用\(f[i][t_0][t_1][t_2]...[t_n]\)来表示\(S\)到了\(i\)位置，\(dp[i][0],dp[i][1],dp[i][2]...dp[i][n]\)分别为\(t_0,t_1,t_2,t_n\)的方案数。

然后发现时间和空间都会炸。所以考虑状压

根据求\(lcs\)的式子可以看出，\(dp[i][j]\)最多只会比\(dp[i][j-1]\)大\(1\)，所以只要把f数组后面的数字差分一下，就变成了可以状压的状态。然后只要前缀和一下就可以还原这个数组。

所以用\(f[i][j]\)来表示\(S\)到了第\(i\)个位置，\(dp\)数组是\(j\)这个状态的方案数。

转移

先预处理出一个\(g\)数组，\(g[i][k]\)表示由\(i\)这个状态，下个位置是\(k\)这个字母，会转移成的状态。

这个预处理其实不难。只要先把i这个状态还原回来。然后用求\(lcs\)那个方法\(dp\)一下。最后再转化回去就可以了。

然后就是\(f\)数组的转移了，只要求出来了\(g\)数组，那么\(f\)数组就比较好处理了。

复杂度是\(O(m2^{|T|})\)

代码

/*

* @Author: wxyww

* @Date:   2019-01-20 10:33:34

* @Last Modified time: 2019-01-20 11:40:43

*/

#include<cstdio>

#include<iostream>

#include<cstdlib>

#include<cmath>

#include<cstring>

#include<ctime>

#include<bitset>

using namespace std;

typedef long long ll;

const int N = 1<<15,mod = 1e9 + 7;

ll read() {

   ll x=0,f=1;char c=getchar();

   while(c<'0'||c>'9') {

      if(c=='-') f=-1;

      c=getchar();

   }

   while(c>='0'&&c<='9') {

      x=x*10+c-'0';

      c=getchar();

   }

   return x*f;

}

char s[20];

int f[1005][N];

int n,tot,ss[20],tmp[2][20],sta[N][4];

void pre(int x) {

   for(int i = 1;i <= n;++i) {

      tmp[0][i] = (x >> (n - i) & 1) + tmp[0][i - 1];

   }

   for(int k = 0;k <= 3;++k) {

      memset(tmp[1],0,sizeof(tmp[1]));

      for(int i = 1;i <= n;++i) {

         tmp[1][i] = max(tmp[0][i],tmp[1][i - 1]);

         if(ss[i] == k)

            tmp[1][i] = max(tmp[1][i],tmp[0][i - 1] + 1);

      }

      int z = 0;

      for(int i = 1;i <= n;++i)

         z = z << 1 | (tmp[1][i] - tmp[1][i - 1]);

      sta[x][k] = z;

   }

}

int ans[N];

int calc(int x){

   int re = 0;

   while(x) {

      re += x & 1;

      x >>= 1;

   }

   return re;

}

int main() {

   int T = read();

   while(T--) {

      memset(f,0,sizeof(f));

      scanf("%s",s + 1);

      n = strlen(s + 1);

      int m = read();

      for(int i = 1;i <= n;++i) {

         if(s[i] == 'A') ss[i] = 0;

         else if(s[i] == 'C') ss[i] = 1;

         else if(s[i] == 'G') ss[i] = 2;

         else ss[i] = 3;

      }

      tot = (1 << n) - 1;

      f[0][0] = 1;

      for(int i = 0;i <= tot;++i) pre(i);

      for(int i = 1;i <= m;++i)

         for(int j = 0;j <= tot;++j)

            for(int k = 0;k < 4;++k)

               f[i][sta[j][k]] += f[i - 1][j],f[i][sta[j][k]] %= mod;

      memset(ans,0,sizeof(ans));

      for(int i = 0;i <= tot;++i) {

         int z = calc(i);

         ans[z] += f[m][i],ans[z] %= mod;

      }

      for(int i = 0;i <= n;++i) {

         printf("%d\n",ans[i]);

      }

   }

   return 0;

}

/*

2

GTC

10

GTC

10

*/