【bzoj3864】Hero meet devil 题解

题目大意

  给你一个只由 AGCT 组成的字符串 $S$，对于每个 $0 \leq i \leq |S|$，问有多少个只由 AGCT 组成的长度为 $m$ 的字符串 $T$，使得 $LCS(S,T)=i$。

  $|S| \leq 15,~m \leq 1000$

题解

  直到大学了才初见 dp 套 dp 呢。。这该是有多菜呢？

  假设已经拥有了一个 $T$，则可以 $O(nm)$ 求出 $LCS$：

$$LCS_{i,j}=\max\{LCS_{i-1,j},~LCS_{i,j-1},~LCS_{i-1,j-1}+1(S_i==T_j)\}$$

  并且，对于 $T$ 的某一位（假设第 $j$ 位）的 dp，相邻的两个 $i$ 所对应的 $LCS_{i,j}$ 最多相差 $1$。也就是说，对于某一位 $j$，由 $LCS_{1,j},~LCS_{2,j},~...~,~LCS_{n,j}$ 构成的 dp 状态最多 $2^{15}$ 种。

  现在没有 $T$，则 dp 这个 T。设 $f_{j,s}$ 表示到了 $T$ 的第 $j$ 位，dp 状态为 $s$，的方案数。预处理各方案的转移 $T_{s,k}$（$k\in\{A,T,C,G\}$），就可以 $O(m\cdot2^{|S|})$ dp 了。

代码

#include<bits/stdc++.h>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
using namespace std;

typedef long long LL;

const int maxm=1005, maxN=32800;
const LL mo=1e9+7;

int n,m,N,er[20];
char S[20];

LL f[2][maxN];
int Q,fn[maxm][2],T[maxN][4],cnt[maxN];
char tb[4]={'A','G','C','T'};
int main()
{
	fo(i,0,14) er[i]=1<<i;
	
	scanf("%d",&Q);
	while (Q--)
	{
		scanf("%s",S+1);
		n=strlen(S+1);
		scanf("%d",&m);
		
		N=(1<<n)-1;
		fo(s,0,N)
		{
			fo(k,0,3)
			{
				fo(i,1,n) fn[i][0]=fn[i-1][0]+((s&er[n-i])>0);
				fo(i,1,n) fn[i][1]=max(max(fn[i-1][1],fn[i][0]),(S[i]==tb[k])?fn[i-1][0]+1:0);
				int news=0;
				fd(i,n,1) fn[i][1]-=fn[i-1][1], news|=(fn[i][1]<<(n-i));
				T[s][k]=news;
				cnt[s]=fn[n][0];
			}
		}
		
		memset(f,0,sizeof(f));
		f[0][0]=1;
		int now=0;
		fo(i,0,m-1)
		{
			memset(f[now^1],0,sizeof(f[now^1]));
			fo(s,0,N)
				fo(k,0,3)
				{
					LL *p=&f[now^1][T[s][k]];
					*p+=f[now][s];
					*p=(*p>=mo) ?*p-mo :*p ;
				}
			now^=1;
		}
		
		fo(i,0,n)
		{
			LL ans=0;
			fo(s,0,N) if (cnt[s]==i) (ans+=f[now][s])%=mo;
			printf("%lld\n",ans);
		}
	}
}