BZOJ 3864 Hero Meets Devil

题目大意

给定一个由AGCT组成的串(t), 求对于所有的(L in [1, |t|]), 有多少个由AGCT组成的串(s)满足(LCS(s, t) = L).

Solution

传说中的DP套DP.

我们用(f_{i, j})表示(s)的前(i)位与(t)的前(j)位的最长公共子序列, 则我们有

则(LCS(s, t) = f[|S|][|T|]).

逐位考虑(s), 假设当前到(s)的第(i)位, 我们用(F)表示状态: (F = { f[i][1], f[i][2], cdots, f[i][|t|] }). 考虑当(i)变成(i + 1)时, (F)会怎么变化: 对于确定的(t), (F)的变化只与(s[i + 1])有关, 因此我们令(c =s[i + 1]), 用(T(F, c))表示当(s[i + 1] = c)时(F)会变成怎么样.

我们用(g[i][F])表示(s)的前(i)位与(t)的最长公共子序列状态为(F)的串(s)的数量, 则对于每一个(c), 有(g[i + 1][T(F, c)] += g[i][F]).

我们发现(F)不容易被记录, 又因为注意到(0 le F[i] - F[i - 1] le 1)且(F[0] = 0), 因此我们用(S)来表示({ F[i] - F[i - 1] })的状态集合. 这样我们就可以轻易地进行状态压缩了.

考虑怎么统计答案:

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 15, MOD = (int)1e9 + 7;
int t[N + 7];
int n, m;
int main()
{

#ifndef ONLINE_JUDGE

	freopen("gene.in", "r", stdin);
	freopen("gene.out", "w", stdout);
	
#endif

	int T; scanf("%d
", &T);
	for (int cs = 0; cs < T; ++ cs)
	{
		static char str[N + 7]; scanf("%s", str + 1);
		n = strlen(str + 1); scanf("%d
", &m);
		for (int i = 1; i <= n; ++ i)
			if (str[i] == 'A') t[i] = 1;
			else if (str[i] == 'T') t[i] = 2;
			else if (str[i] == 'G') t[i] = 3;
			else if (str[i] == 'C') t[i] = 4;
		static int trans[(1 << N) + 7][7];
		for (int j = 0; j < 1 << n; ++ j) for (int c = 1; c <= 4; ++ c)
		{
			static int a[N + 7], b[N + 7];
			memset(a, 0, sizeof a);
			for (int k = 0; k < n; ++ k) a[k + 1] = a[k] + (j >> k & 1);
			b[0] = 0;
			for (int k = 1; k <= n; ++ k) b[k] = max(max(a[k], b[k - 1]), a[k - 1] + (c == t[k]));
			int stt = 0;
			for (int k = 0; k < n; ++ k) if (b[k + 1] - b[k]) stt |= 1 << k;
			trans[j][c] = stt;
		}
		static int f[(1 << N) + 7], g[(1 << N) + 7];
		memset(f, 0, sizeof f); f[0] = 1;
		for (int i = 0; i < m; ++ i)
		{
			memset(g, 0, sizeof g);
			for (int j = 0; j < 1 << n; ++ j) if (f[j]) for (int c = 1; c <= 4; ++ c)
				g[trans[j][c]] = (g[trans[j][c]] + f[j]) % MOD;
			swap(f, g);
		}
		static int ans[N + 7];
		memset(ans, 0, sizeof ans);
		for (int i = 0; i < 1 << n; ++ i)
		{
			int cnt = 0;
			for (int tmp = i; tmp; tmp >>= 1) if (tmp & 1) ++ cnt;
			ans[cnt] = (ans[cnt] + f[i]) % MOD;
		}
		for (int i = 0; i <= n; ++ i) printf("%d
", ans[i]);
	}
}