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 ...
Submit: 397 Solved: 206
[Submit][Status][Discuss]
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
1GTC
10
Sample Output
122783
528340
497452
HINT
Source
首先想一下LCS的轉移方程
$$lcs[i][j]=max \begin{cases} lcs[i-1][j-1]+1 & \text{if t[i]=s[j]} \\ lcs[i-1][j] \\ lcs[i][j-1] \end{cases}$$
這樣的話，當$i$確定是，$lcs[i][j]$和$lcs[i][j-1]$最多相差$1$
且題目中說$|S|<= 15$，因此我們考慮把差分後的lcs數組狀壓起來
那麼如何統計答案呢？
設$f[i][sta]$表示在第$i$個位置，此時lcs的狀態為$sta$的方案數，
然後我們枚舉一下這個位置選ACGT中的哪個
設$trans[sta'][A/C/G/T]$為在$sta$狀態表示的lcs後加了ACGT中的一個後的狀態，這個很顯然可以預處理得到
那麼轉移方程為
$$f[i][ trans[sta][k] ] += f[i - 1][sta] $$
$$f[0][0] = 1$$
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int MAXN = 1001, mod = 1e9 + 7; char S[16], SS[] = {"ACGT"}; int a[16], f[MAXN][(1 << 15) + 2], trans[(1 << 15) + 2][5], N, Len, limit, ans[111]; int tmp[2][16]; int solve(int sta, int ch) { int ret = 0; memset(tmp, 0, sizeof(tmp)); for(int i = 0; i < N; i++) tmp[0][i + 1] = tmp[0][i] + ((sta >> i) & 1 ); for(int i = 1; i <= N; i++) { int mx = 0; if(a[i] == ch) mx = tmp[0][i - 1] + 1; mx = max( max(mx, tmp[0][i]), tmp[1][i-1]); tmp[1][i] = mx; } for(int i = 0; i < N; i++) ret += (1 << i) * (tmp[1][i + 1] - tmp[1][i]); return ret; } int main() { #ifdef WIN32 freopen("a.in", "r", stdin); #endif int QWQ;scanf("%d", &QWQ); while(QWQ--) { memset(f, 0, sizeof(f));memset(ans, 0, sizeof(ans)); scanf("%s", S + 1); N = strlen(S + 1); limit = (1 << N) - 1; for(int i = 1; i <= N; i++) for(int j = 0; j < 4; j++) if(S[i] == SS[j]){a[i] = j + 1;break;} scanf("%d", &Len); f[0][0] = 1; for(int sta = 0; sta <= limit; sta++) for(int j = 1; j <= 4; j++) trans[sta][j] = solve(sta, j); for(int i = 1; i <= Len; i++) for(int sta = 0; sta <= limit; sta++) for(int k = 1; k <= 4; k++) f[i][ trans[sta][k] ] = (f[i][ trans[sta][k] ] + f[i - 1][sta]) % mod; for(int sta = 0; sta <= limit; sta++) ans[__builtin_popcount(sta)] = (ans[__builtin_popcount(sta)] + f[Len][sta]) % mod; //這個函數是算出sta中1的個數 for(int i = 0; i <= N; i++) printf("%d\n", ans[i] % mod); } return 0; }
