Chro's Blog


同じ世界に、立っていたんだ。


「BZOJ 3864」「HDU 4899」Hero meet devil

  1. 1. Description
  2. 2. Input
  3. 3. Output
  4. 4. Sample Input
  5. 5. Sample Output
  6. 6. Solution

Description

There is an old country and the king fell in love with a devil. The devil always asks the king to do some crazy things. Although the king used to be wise and beloved by his people. Now he is just like a boy in love and can’t refuse any request from the devil. Also, this devil is looking like a very cute Loli.

After the ring has been destroyed, the devil doesn’t feel angry, and she is attracted by z*p’s wisdom and handsomeness. So she wants to find z*p out.

But what she only knows is one part of z*p’s DNA sequence S leaving on the broken ring.

Let us denote one man’s DNA sequence as a string consist of letters from ACGT. The similarity of two string S and T is the maximum common subsequence of them, denote by LCS(S,T).

After some days, the devil finds that. The kingdom’s people’s DNA sequence is pairwise different, and each is of length m. And there are 4^m people in the kingdom.

Then the devil wants to know, for each 0 <= i <= |S|, how many people in this kingdom having DNA sequence T such that LCS(S,T) = i.

You only to tell her the result modulo 10^9+7.

Input

The first line contains an integer T, denoting the number of the test cases.

For each test case, the first line contains a string S. the second line contains an integer m.

T<=5

|S|<=15. m<= 1000.

Output

For each case, output the results for i=0,1,…,|S|, each on a single line.

Sample Input

1
2
3
1
GTC
10

Sample Output

1
2
3
4
1
22783
528340
497452

Solution

第一次做 DP 套 DP,感觉不是那么难,还有就是做法实在太神辣~学习一个!


考虑普通的 LCS 问题怎么做。

若有序列 S[1..n], T[1..m],那么我们可以用 dp[i][j] 表示 S[1..i], T[1..j] 的最长公共子序列,并在 S[i]==T[j] 时它等于 dp[i-1][j-1] + 1,其他时候等于 dp[i-1][j]、dp[i][j-1] 中的较大值。

注意到,对于 dp[i][*] 这一整行而言,序列非严格单调递增,并且相邻位置最多相差 1。

那么我们可以把这一行 dp 值差分一下,变成一个 n 位二进制数 S,用它作为接下来预处理的状态。(不要忘记 LCS 的 DP 是可以滚动数组优化空间的,因此前面的那些行都没用)

然后我们套用传统的 LCS 思路进行预处理:(注意,以下文字说明的变量名含义始终一致,而且与后面代码不一致,不要搞混了)

  • 枚举状态 S,用 f[i] 表示 S 的二进制最低 i+1 位有多少个 1。
    • 这等价于计算出 dp[i-1][*] 这完整的一行。
    • f[n] 就是 S 的二进制中 1 的个数。
  • 枚举要添加哪个字符,然后按照传统的 LCS 计算出 dp[i][*],记为数组 g。
  • 把数组 g 差分得到新的状态 S’,那么记 trans[S][k] = S’,也就是说在一个状态为 S 的序列后面添加一个字符 k,得到的新状态为 S’。

余下部分的 DP 非常简单: h[i][S] 表示长度为 i 的基因串的 LCS DP 滚动数组状态为 S 的方案数。边界条件是 h[0][0]=1(空串)。转移是 h[i+1][trans[S][k]] += h[i][S]。

统计最终答案。题目要求输出 LCS 为 0..n 时的每个方案数。当 LCS 长度为 i 时,差分的状态恰好包含 i 个二进制位。

也就是说,$ans[i]=\sum_{popcount(S)=i}h[m][S]$

做完了。再次提醒,代码中的变量定义跟上面不太一样!

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
#include <bits/stdc++.h>
using namespace std;
const int maxn = 17;
const int maxs = 32769;
const int mod = 1000000007;
const char T[4] = {'A', 'C', 'G', 'T'};
int n, m, full;
int trans[maxs][4];
int dp[2][maxs], ans[maxn];
int cnt[maxs], f[maxn], g[maxn];
char S[maxn];
void preprocessor() {
for (int i = 0; i <= full; ++i) {
f[0] = 0;
for (int j = 0; j < n; ++j) f[j + 1] = f[j] + (i >> j & 1);
cnt[i] = f[n];
for (int k = 0; k < 4; ++k) {
for (int j = 1; j <= n; ++j) {
g[j] = max(g[j - 1], f[j]);
if (T[k] == S[j]) g[j] = max(g[j], f[j - 1] + 1);
}
trans[i][k] = 0;
for (int j = 0; j < n; ++j) if (g[j + 1] - g[j]) trans[i][k] |= 1 << j;
}
}
}
void kase() {
scanf("%s%d", S + 1, &m);
n = strlen(S + 1), full = (1 << n) - 1;
preprocessor();
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 j = 0; j <= full; ++j) for (int k = 0; k < 4; ++k)
(dp[i & 1][trans[j][k]] += dp[~i & 1][j]) %= mod;
}
memset(ans, 0, sizeof ans);
for (int i = 0; i <= full; ++i) (ans[cnt[i]] += dp[m & 1][i]) %= mod;
for (int i = 0; i <= n; ++i) printf("%d\n", ans[i]);
}
int main() {
int T;
for (scanf("%d", &T); T--; ) kase();
return 0;
}
最近的文章

「BZOJ 1025」「SCOI2009」游戏

Descriptionwindy学会了一种游戏。对于1到N这N个数字,都有唯一且不同的1到N的数字与之对应。最开始windy把数字按顺序1,2,3,……,N写一排在纸上。然后再在这一排下面写上它们对应的数字。然后又在新的一排下面写上它们对应的数字。如此反复,直到序列再次变为1,2,3,……,N。 如…

BZOJ, 群论, 背包 DP 继续阅读
更早的文章

「BZOJ 4585」「UOJ 205」「APIO2016」Fireworks

烟花表演是最引人注目的节日活动之一。在表演中,所有的烟花必须同时爆炸。为了确保安全,烟花被安置在远离开关的位置上,通过一些导火索与开关相连。导火索的连接方式形成一棵树,烟花是树叶,如图所示。火花从开关出发,沿导火索移动。每当火花抵达一个分叉点时,它会扩散到与之相连的所有导火索,继续燃烧。导火索燃烧的…

BZOJ, UOJ, 可合并堆, 树型 DP 继续阅读