1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63
|
#include <cstring> #include <algorithm> using namespace std;
const int MOD = 1e9+7; int dp[1001][(1<<15)+2],to[(1<<15)+2][4],t,m,n,tmp[2][16],S[16]; long long ans[16]; char mids[16]; int (int state,int alpha){ memset(tmp,0,sizeof(tmp)); for(int i=0;i<n;i++) tmp[0][i+1]=tmp[0][i]+((state&(1<<i))==(1<<i)); for(int i=1;i<=n;i++) tmp[1][i]=max(tmp[0][i-1]+(S[i]==alpha),max(tmp[0][i],tmp[1][i-1])); int ans=0,last=0; for(int i=1;i<=n;i++){ ans+=((last!=tmp[1][i])<<(i-1)); last=tmp[1][i]; } return ans; } int toi(char c){ switch (c){ case 'A':return 0; case 'G':return 1; case 'C':return 2; case 'T':return 3; }; } int bitcount(int x){ int ans=0; while(x){ ans++; x&=(x-1); } return ans; } int main(){ scanf("%d",&t); while(t--){ memset(dp,0,sizeof(dp)); memset(to,0,sizeof(to)); dp[0][0]=1; scanf("%s %d",mids,&m); n=strlen(mids); for(int i=1;i<=n;i++) S[i]=toi(mids[i-1]); for(int i=0;i<(1<<n);i++) for(int j=0;j<=3;j++) to[i][j]=calto(i,j); for(int q=1;q<=m;q++) for(int i=0;i<(1<<n);i++) for(int j=0;j<=3;j++) dp[q][to[i][j]]=(dp[q][to[i][j]]+dp[q-1][i])%MOD; memset(ans,0,sizeof(ans)); for(int i=0;i<(1<<n);i++) ans[bitcount(i)]=(ans[bitcount(i)]+dp[m][i])%MOD; for(int i=0;i<=n;i++) printf("%lldn",ans[i]); } return 0; }
|
近期评论