还是来存个dp套dp模板吧
题意是给你一个由ATGC组成的字符串，长度n<=15，求长度为m（<=1000）的字符串里有多少个满足与原串的最长公共子序列长度为i，i取0到n所有值
考虑暴力，枚举所有长为m的字符串，dp求LCS
不说了时间复杂度绝对爆炸
来考虑递推式 ：dp[i][j]=max(max(dp[i-1][j],dp[i][j-1]),dp[i-1][j-1]+[a[i]==b[j]]（相等为1不等为0）)
那么，所有的dp[i]中，相邻的j差最多为1
那么，我们可以把它压成状态，dp[i][sta]表示a在第i位，b的状态为sta时的方案数
至于怎么转移这个问题，肯定不能每次枚举对吧
那么就只好预处理出来了，用nxt[sta][j]表示状态为sta，下一步为k时转移到的状态
最后统计状态sta中有多少个1，因为我们存的是差分结果，所以累加起来就是最后一位时的最长公共子序列长度（可以回忆最初的递推式，最初时的dp[n][m]就是LCS长度，对吧）（__builtin_popcount(i)是输出i转成2进制由多少个1），枚举一遍状态，统计入对应答案，然后就可以输出了
代码一如既往地难看
#include<bits/stdc++.h> #include<cstdio> #include<cmath> #include<cstring> #include<cstdlib> #include<algorithm> #include<queue> #include<deque> #include<list> #include<set> #include<vector> #include<iostream> #define ll int #define re register #define inf 0x3f3f3f3f #define inl inline #define sqr(x) (x*x) //#define eps 1e-8 #define debug printf("debug "); //#pragma comment(linker, "/STACK:1024000000,1024000000") //#pragma GCC optimize (2) //#pragma G++ optimize (2) using namespace std; const ll mod=1e9+7; const ll MSTA=1<<15; const ll MAXN=20; inl ll read() { re ll x = 0; re int f = 1; char ch = getchar(); while(ch<'0'||ch>'9') { if(ch== '-' ) f = -1; ch = getchar(); } while(ch>='0'&&ch<='9') {x=(x<<1)+(x<<3)+(ch^48);ch=getchar();} return x * f; } inl char readc() { char ch=getchar(); while(('z'<ch||ch<'a')&&('Z'<ch||ch<'A')) ch=getchar(); return ch; } inl void write(re ll x){ if(x>=10)write(x/10); putchar(x%10+'0'); } inl void writeln(re ll x){ if(x<0) {x=-x;putchar('-');} write(x); puts(""); } inl ll gcd(re ll x,re ll y){while(y^=x^=y^=x%=y);return x;} inl void FR() { freopen(".in","r",stdin); freopen(".out","w",stdout); } inl void FC() { fclose(stdin); fclose(stdout); } char ss[MAXN],dna[10]={'A','T','G','C'}; ll m,n,nxt[MSTA][10],dp[5][MSTA],ans[MAXN]; void init() { ll f[MAXN],g[MAXN]; for(re ll i=0;i<(1<<n);i++) { memset(f,0,sizeof(f)); memset(g,0,sizeof(g)); for(re ll j=1;j<=n;j++) f[j]=f[j-1]+((i>>(j-1))&1); for(re ll k=0;k<4;k++) { for(re ll j=1;j<=n;j++) { g[j]=max(g[j-1],f[j]); if(dna[k]==ss[j]) g[j]=max(g[j],f[j-1]+1); } nxt[i][k]=0; for(re ll j=0;j<n;j++) { if(g[j+1]-g[j]) { nxt[i][k]|=(1<<j); } } } } } int main() { // FR(); re ll T=read(); while(T--) { scanf("%s",ss+1); n=strlen(ss+1); m=read();init(); memset(dp,0,sizeof(dp)); dp[0][0]=1; bool flag=0; for(re ll i=1;i<=m;i++) { flag^=1; memset(dp[flag],0,sizeof(dp[flag])); for(re ll j=0;j<(1<<n);j++) { for(re ll k=0;k<4;k++) { dp[flag][nxt[j][k]]=(dp[flag][nxt[j][k]]+dp[flag^1][j])%mod; } } } memset(ans,0,sizeof(ans)); for(re ll i=0;i<(1<<n);i++) { ans[__builtin_popcount(i)]=(ans[__builtin_popcount(i)]+dp[m&1][i])%mod; } for(re ll i=0;i<=n;i++) writeln(ans[i]); } // FC(); return 0; }