【DP】BZOJ3864 Hero meet devil

分析：

YY了一个做法，没想到真的能过。。。（太乱来了）

观察常规的最长公共子序列问题的DP方式：DP[i][j]表示第1个串匹到i位置，第2个串匹到j位置的最长公共子序列长度。

然后有个很显然的性质：
$DP[i][j?1]\le DP[i][j]\le DP[i][j?1]+1$

所以可以把$DP[i][0]、DP[i][1]、DP[i][2]\dots \dots DP[i][|S|]$都表示出来，根据上面的性质，差分一下就可以了。

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define SF scanf
#define PF printf
#define MAXN 1010
#define MAXK (1<<15)
#define MOD 1000000007
using namespace std;
int tran[MAXK][4];
char s[MAXN];
int len,m;
int pres[MAXN],newp[MAXN];
char letter[6]={
    'A','G','C','T'};
void prepare(){
    for(int i=0;i<(1<<len);i++){
    for(int j=0;j<len;j++)pres[j]=(i>>j)&1;for(int j=1;j<len;j++)pres[j]+=pres[j-1];for(int nxt=0;nxt<4;nxt++){
    for(int j=0;j<len;j++){
    newp[j]=pres[j];if(j!=0)newp[j]=max(newp[j],newp[j-1]);if(s[j]==letter[nxt]){
    if(j!=0)newp[j]=max(newp[j],pres[j-1]+1);elsenewp[j]|=1;}}int mask=newp[0];for(int j=1;j<len;j++)mask|=(1<<j)*(newp[j]-newp[j-1]);tran[i][nxt]=mask;}}
}
int count_one(int x){
    int sum=0;while(x){
    if(x&1)sum++;x>>=1;}return sum;
}
int dp[2][MAXK],ans[MAXN];
int main(){
    int t;SF("%d",&t);while(t--){
    SF("%s",s);len=strlen(s);prepare();SF("%d",&m);int now=0;memset(dp,0,sizeof dp);dp[now][0]=1;for(int i=1;i<=m;i++){
    memset(dp[now^1],0,sizeof dp[now^1]);for(int mask=0;mask<(1<<len);mask++)for(int nxt=0;nxt<4;nxt++){
    int mask1=tran[mask][nxt];dp[now^1][mask1]=(dp[now^1][mask1]+dp[now][mask])%MOD;}now^=1;}memset(ans,0,sizeof ans);for(int i=0;i<(1<<len);i++)(ans[count_one(i)]+=dp[now][i])%=MOD;for(int i=0;i<=len;i++)PF("%d\n",ans[i]);}	
}