P10614 BZOJ3864 Hero meet devil 题解

· · 题解

upd 2024.9.5：感谢 @Auferstanden 指出的代码错误，发现是 ans[0] 忘清空了，已修改。

欸这题啥时候登陆洛谷了，抢下第一篇题解！

经典 DP 套 DP 题目。

这道题的内层 DP 是 LCS，我们不妨想 LCS 的转移方程：

设 g_{i,j} 为串 s 的前 i 位和串 t 前 j 位的 LCS，则

g_{i,j}= \begin{cases} g_{i-1,j-1}+1&s_i=t_j\\ \max(g_{i-1,j},g_{i,j-1})&s_i\ne t_j \end{cases}

因此一个朴素的想法就是，设 f_{i,S} 表示考虑串 t 的前 i 位，与串 S 的 LCS 数组为 S 的方案数。转移的时候考虑下一位放啥，然后先把 S 转移到 S'，再从 f_{i,S} 转移到 f_{i+1,S'} 即可。

其实到这里已经可以了，这个 DP 看着状态数很恐怖，实际上状态数很少。

考虑在 i 固定的时候，g_i 这一行的差分数组。根据转移方程可知，差分数组只有 0/1 两种数，又因为差分数组和 g_i 这一行是双射，所以第二维大小最多为 2^{|S|}。

而且既然发现差分数组只有 0/1，那直接状压记第二维即可。

#include<bits/stdc++.h>
bool Mst;
#define in(S,i) (((S)>>((i)-1))&1)
#define rep(x,qwq,qaq) for(int (x)=(qwq);(x)<=(qaq);++(x))
using namespace std;
#define mod 1000000007
int T;
int n,m;
string s;
#define maxm 1010
int f[maxm][(1<<15)];
int g[20],h[20];
void add(int &x,int y) {
    x+=y;
    if(x>=mod)x-=mod;
}
int a[20];
int append(int S,int nxt) {
    rep(i,1,n)g[i]=g[i-1]+in(S,i);
    rep(i,1,n) {
        if(a[i]==nxt)h[i]=g[i-1]+1;
        else h[i]=max({h[i-1],g[i]});
    }
    int reS=0;
    rep(i,1,n)reS+=(1<<(i-1))*(h[i]-h[i-1]);
    return reS;
}
int ans[20];
int nxt[(1<<15)][5];
void solve() {
    cin>>s>>m;
    n=s.length();
    s=" "+s;
    rep(i,1,n) {
        switch(s[i]) {
            case 'A':
                a[i]=1;
                break;
            case 'C':
                a[i]=2;
                break;
            case 'G':
                a[i]=3;
                break;
            case 'T':
                a[i]=4;
                break;
        }
    }
    rep(S,0,(1<<n)-1)rep(i,1,4)nxt[S][i]=append(S,i);
    f[0][0]=1;
    rep(i,0,m-1) {
        rep(S,0,(1<<n)-1) {
            if(f[i][S]==0)continue;
            add(f[i+1][nxt[S][1]],f[i][S]);
            add(f[i+1][nxt[S][2]],f[i][S]);
            add(f[i+1][nxt[S][3]],f[i][S]);
            add(f[i+1][nxt[S][4]],f[i][S]);
            f[i][S]=0;
        }
    }
    rep(i,0,n)ans[i]=0;
    rep(S,0,(1<<n)-1) {
        add(ans[__builtin_popcount(S)],f[m][S]);
        f[m][S]=0;
    }
    rep(i,0,n)cout<<ans[i]<<'\n';
}
bool Med;
signed main() {
    cerr<<(&Mst-&Med)/1024.0/1024.0<<" MB\n";
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>T;
    while(T--)solve();
    return 0;
}