传送阵：http://acm.hdu.edu.cn/showproblem.php?pid=4899
题目大意：给定一个DNA序列，求有多少长度为m的序列与该序列的最长公共子序列长度为0,1...|S|;
分析：
我们可以考虑对于求两个串的最长公共子序列的dp：f[i,j]代表第一个串到了i，第二个串到了j的最长公共子序列。对于两个串来说，如果数组f[i]是完全一样的，则它们对后面的影响也是完全一样的，所以我们可以设2维状态：F[i,j]代表我们当前以及到了i，f[i]的状态为j的方案数，但是这样设状态第二维有10^10。我们发现一个f[i,j]一定不会比f[i,j-1]小，且最多比f[i,j-1]多1，所以我们在设状态的时候可以取个差值，就变成2^10了。
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
#define maxn 20
#define mod 1000000007
char dic[]="ACTG";
int add[<<][];
int dp[][<<];
int pre[maxn],lcs[maxn],ans[maxn];
char s[maxn];
int T,n,m;
void Add(int &x,int y){
x+=y;
if(x>=mod)x-=mod;
}
void init(){
scanf("%s",s+);n=strlen(s+);
memset(add,,sizeof(add));
memset(dp,,sizeof(dp));
for(int state=;state<(<<n);++state){
pre[]=;
for(int i=;i<=n;++i)pre[i]=pre[i-]+((state>>(i-))&);
for(int k=;k<;++k){
for(int i=;i<=n;++i)
if(s[i]==dic[k])lcs[i]=pre[i-]+;
else lcs[i]=max(lcs[i-],pre[i]);
int &t=add[state][k];
for(int i=;i<=n;++i)
t|=((lcs[i]!=lcs[i-])<<(i-));
}
}
}
int get(int x){
int s=;
while(x){
s+=x&;
x>>=;
}return s;
}
void work(){
scanf("%d",&m);
int *now=dp[],*next=dp[];
memset(next,,(<<n)*sizeof(int));
next[]=;
for(int i=;i<=m;++i){
swap(now,next);
memset(next,,(<<n)*sizeof(int));
for(int state=;state<(<<n);++state)
if(now[state])
for(int k=;k<;++k)
Add(next[add[state][k]],now[state]);
}
memset(ans,,sizeof(ans));
for(int i=;i<(<<n);++i)
Add(ans[get(i)],next[i]);
for(int i=;i<=n;++i)
printf("%d\n",ans[i]);
}
int main(){
scanf("%d",&T);
while(T--){
init();
work();
}
return ;
}