传送阵：

题目大意：给定一个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
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;#define maxn 20#define mod 1000000007char dic[]="ACTG";int add[1<<15][4];int dp[2][1<<15];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+1);n=strlen(s+1);    memset(add,0,sizeof(add));    memset(dp,0,sizeof(dp));    for(int state=0;state<(1<
           
            >(i-1))&1); for(int k=0;k<4;++k){ for(int i=1;i<=n;++i) if(s[i]==dic[k])lcs[i]=pre[i-1]+1; else lcs[i]=max(lcs[i-1],pre[i]); int &t=add[state][k]; for(int i=1;i<=n;++i) t|=((lcs[i]!=lcs[i-1])<<(i-1)); } }}int get(int x){ int s=0; while(x){ s+=x&1; x>>=1; }return s;}void work(){ scanf("%d",&m); int *now=dp[0],*next=dp[1]; memset(next,0,(1<