简要题意

给你一个只由 AGCTAGCTAGCT 组成的字符串 SSS ，对于每个0≤i≤∣S∣0 \leq i \leq |S|0≤i≤∣S∣，问有多少个只由 AGCTAGCTAGCT 组成的长度为 mmm 的字符串 TTT，使得LCS(S,T)=iLCS(S,T)=iLCS(S,T)=i

SOLUTION

刚开始想的时候，怎么定义状态都会造成重复等各种问题，于是搜题解（emmm）。。。

考虑求LCSLCSLCS时的dpdpdp：定义 lcs[i][j]lcs[i][j]lcs[i][j] 表示AAA串的前iii位与B串的前jjj位的LCSLCSLCS长度

lcs[i][j]=max(lcs[i−1][j−1]+(A[i]==B[i])，lcs[i][j−1]，lcs[i−1][j])lcs[i][j]=max({lcs[i−1][j−1]+ (A[i]==B[i])，lcs[i][j−1]，lcs[i−1][j]})lcs[i][j]=max(lcs[i−1][j−1]+(A[i]==B[i])，lcs[i][j−1]，lcs[i−1][j])
​

可以发现，当 iii 相同时，lcs[i][j]lcs[i][j]lcs[i][j] 与 lcs[i][j+1]lcs[i][j+1]lcs[i][j+1] 最多相差1

把每一位之间的差状压，表示为一个状态进行计数，就可以了

第iii位是111意味着第iii上的字符对lcslcslcs有贡献，即是1的位们就是公共子串部分

定义 dp[i][s]dp[i][s]dp[i][s] 表示：长度为 iii 的字符串，与 SSS 的 lcslcslcs 状态为 sss 的方案数

trans(s,k)trans(s,k)trans(s,k) 表示在 lcslcslcs 状态为 sss 的情况下，在后面添加字符 kkk 转移到的状态

在不同串但是lcslcslcs同种状态的时候，在后面加上同一个字符，转移到的状态是一样的

转移方程：dp[i][trans(s,k)]+=dp[i−1][s]dp[i][trans(s,k)]+=dp[i−1][s]dp[i][trans(s,k)]+=dp[i−1][s]

注意：先想清楚求lcslcslcs的过程在来看这个trans的方程转移

CODE

#include 
using namespace std;
const int M=1e3+2,L=20,N=(1<<15)+2,P=1e9+7;
char ch[]="ACGT";
int T,n,m,dp[2][N],tr[N][4],ans[M],f[L],g[L];
char S[L];
void transwork(){for(int s=0;s<(1<memset(f,0,sizeof f);memset(g,0,sizeof g);for(int j=1;j<=n;j++){f[j]=f[j-1]+((s>>(j-1))&1);}//f[j]=lcs[n][j]for(int k=0;k<4;k++){//要加的字符 for(int j=1;j<=n;j++){g[j]=max(g[j-1],f[j]);if(ch[k]==S[j]){//可以有贡献 g[j]=max(g[j],f[j-1]+1);}//lcs方程过程 }tr[s][k]=0;//trans清0 for(int j=1;j<=n;j++){if(g[j]-g[j-1]){//有贡献 tr[s][k]|=1<<(j-1);}}		}}
}
int main(){scanf("%d",&T);while(T--){scanf("%s%d",S+1,&m);n=strlen(S+1);transwork(); memset(dp,0,sizeof dp);dp[0][0]=1;for(int i=1;i<=m;i++){memset(dp[i&1],0,sizeof dp[i&1]);for(int s=0;s<(1<for(int k=0;k<4;k++){(dp[i&1][tr[s][k]]+=dp[(i&1)^1][s])%=P;}}}memset(ans,0,sizeof ans);for(int s=0;s<(1<(ans[__builtin_popcount(s)]+=dp[m&1][s])%=P;//有多少位为1}for(int i=0;i<=n;i++){printf("%d\n",ans[i]);}}return 0;
}

完结撒花❀

★,°:.☆(￣▽￣)/$:.°★ 。