自动搬运

查看原文

来自洛谷，原作者为

	fairytale 不要忘记我们的歌

搬运于2025-08-24 22:59:39，当前版本为作者最后更新于2024-06-18 23:43:58，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

upd 2024.9.5：感谢 @Auferstanden 指出的代码错误，发现是 ans[0] 忘清空了，已修改。

欸这题啥时候登陆洛谷了，抢下第一篇题解！

经典 DP 套 DP 题目。

这道题的内层 DP 是 LCS，我们不妨想 LCS 的转移方程：

设 $g_{i,j}$ 为串 $s$ 的前 $i$ 位和串 $t$ 前 $j$ 位的 LCS，则

$$g_{i,j}= \begin{cases} g_{i-1,j-1}+1&s_i=t_j\\ \max(g_{i-1,j},g_{i,j-1})&s_i\ne t_j \end{cases} $$

因此一个朴素的想法就是，设 $f_{i,S}$ 表示考虑串 $t$ 的前 $i$ 位，与串 $S$ 的 LCS 数组为 $S$ 的方案数。转移的时候考虑下一位放啥，然后先把 $S$ 转移到 $S'$，再从 $f_{i,S}$ 转移到 $f_{i+1,S'}$ 即可。

其实到这里已经可以了，这个 DP 看着状态数很恐怖，实际上状态数很少。

考虑在 $i$ 固定的时候，$g_i$ 这一行的差分数组。根据转移方程可知，差分数组只有 $0/1$ 两种数，又因为差分数组和 $g_i$ 这一行是双射，所以第二维大小最多为 $2^{|S|}$。

而且既然发现差分数组只有 $0/1$，那直接状压记第二维即可。

#include<bits/stdc++.h>
bool Mst;
#define in(S,i) (((S)>>((i)-1))&1)
#define rep(x,qwq,qaq) for(int (x)=(qwq);(x)<=(qaq);++(x))
using namespace std;
#define mod 1000000007
int T;
int n,m;
string s;
#define maxm 1010
int f[maxm][(1<<15)];
int g[20],h[20];
void add(int &x,int y) {
	x+=y;
	if(x>=mod)x-=mod;
}
int a[20];
int append(int S,int nxt) {
	rep(i,1,n)g[i]=g[i-1]+in(S,i);
	rep(i,1,n) {
		if(a[i]==nxt)h[i]=g[i-1]+1;
		else h[i]=max({h[i-1],g[i]});
	}
	int reS=0;
	rep(i,1,n)reS+=(1<<(i-1))*(h[i]-h[i-1]);
	return reS;
}
int ans[20];
int nxt[(1<<15)][5];
void solve() {
	cin>>s>>m;
	n=s.length();
	s=" "+s;
	rep(i,1,n) {
		switch(s[i]) {
			case 'A':
				a[i]=1;
				break;
			case 'C':
				a[i]=2;
				break;
			case 'G':
				a[i]=3;
				break;
			case 'T':
				a[i]=4;
				break;
		}
	}
	rep(S,0,(1<<n)-1)rep(i,1,4)nxt[S][i]=append(S,i);
	f[0][0]=1;
	rep(i,0,m-1) {
		rep(S,0,(1<<n)-1) {
			if(f[i][S]==0)continue;
			add(f[i+1][nxt[S][1]],f[i][S]);
			add(f[i+1][nxt[S][2]],f[i][S]);
			add(f[i+1][nxt[S][3]],f[i][S]);
			add(f[i+1][nxt[S][4]],f[i][S]);
			f[i][S]=0;
		}
	}
	rep(i,0,n)ans[i]=0;
	rep(S,0,(1<<n)-1) {
		add(ans[__builtin_popcount(S)],f[m][S]);
		f[m][S]=0;
	}
	rep(i,0,n)cout<<ans[i]<<'\n';
}
bool Med;
signed main() {
	cerr<<(&Mst-&Med)/1024.0/1024.0<<" MB\n";
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>T;
	while(T--)solve();
	return 0;
}