双倍经验题

同BZOJ5336

#include
     
      #include
      
       #include
       
        using namespace std;const int mod=1e9+7;int n,K,now[25],G[25],To[50005][4],F[2][50005],ED[50005],ANS[25],S[25];char s[1000005];void dfs(int t,int s){	if (t>K){		for (int i=1; i<=K; i++) {			now[i]=now[i-1];			if (s&(1<
        
         =1; i--) (To[s][to]<<=1)|=(G[i]-G[i-1]);		}		return;	}	dfs(t+1,s<<1);	dfs(t+1,s<<1|1);}int main(){	int T;	scanf("%d",&T);	while (T--){		scanf("%s",s+1);		K=strlen(s+1);		scanf("%d",&n);		for (int i=1; i<=K; i++){			if (s[i]=='A') S[i]=0;			else if (s[i]=='C') S[i]=1;			else if (s[i]=='G') S[i]=2;			else S[i]=3;		}		memset(To,0,sizeof(To));		dfs(1,0);		memset(F,0,sizeof(F));		F[0][0]=1;		for (int i=0; i