Luogu

LOJ

分析

发现题目中那个 LCS 的限制不好处理，考虑建一个自动机来解决这个问题。

假设我们已经建出了自动机，我们就可以设 $f_{i,j,k}$ 为前 $i$ 个字符，已经转移到自动机的 $j$ 节点，已经匹配到了 NOI 的第 $k$ 位的方案数，然后根据 $k$ 转移即可。

现在考虑如何建这个自动机。考虑求两个串的 LCS 的过程，即设 $g_{i,j}$ 表示第一个串匹配到 $i$、第二个串匹配到 $j$ 的 LCS 的长度。现在一个串已知，所以在自动机上转移一次只需要知道 $g_{i-1,x}$ 和新加入的字符。于是我们想到将每种 $g_{i,x}$ 作为状态。注意到 $g_{i,x}$ 不降且一次最多增加 $1$，所以可以状压其差分数组作为状态。

可以不先处理出自动机，而是在转移 $f$ 时还原出 $g$ 的值然后转移 $g$ 得到新的节点。（所以叫做 DP 套 DP？）

代码

// ====================================
//   author: M_sea
//   website: https://m-sea-blog.com/
// ====================================
#include <bits/stdc++.h>
#define file(x) freopen(#x".in","r",stdin); freopen(#x".out","w",stdout)
#define popcount(S) __builtin_popcount(S)
using namespace std;
typedef long long ll;

int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=1000+10;
const int mod=1e9+7;

int n,k,tot,ans[N]; char s[N];
int f[2][1<<15][3],g[2][N];

void decode(int S) {
    for (int i=1;i<=k;++i) g[0][i]=(S>>(i-1))&1;
    for (int i=1;i<=k;++i) g[0][i]+=g[0][i-1];
}
int encode() {
    int S=0;
    for (int i=1;i<=k;++i)
        if (g[1][i]-g[1][i-1]) S|=1<<(i-1);
    return S;
}

void trans(int nxt,int S,int l,char c,int w) {
    decode(S);
    for (int i=1;i<=k;++i) {
        g[1][i]=max(g[1][i-1],g[0][i]);
        if (c==s[i]) g[1][i]=max(g[1][i],g[0][i-1]+1);
    }
    int j=encode();
    f[nxt][j][l]=(f[nxt][j][l]+w)%mod;
}

int main() {
    n=read(),k=read(),tot=1<<k; scanf("%s",s+1);
    f[0][0][0]=1;
    for (int i=0;i<n;++i) {
        int now=i&1,nxt=now^1;
        memset(f[nxt],0,sizeof(f[nxt]));
        for (int j=0;j<tot;++j) {
            if (f[now][j][0]) {
                trans(nxt,j,1,'N',f[now][j][0]);
                trans(nxt,j,0,'O',f[now][j][0]);
                trans(nxt,j,0,'I',f[now][j][0]);
            }
            if (f[now][j][1]) {
                trans(nxt,j,1,'N',f[now][j][1]);
                trans(nxt,j,2,'O',f[now][j][1]);
                trans(nxt,j,0,'I',f[now][j][1]);
            }
            if (f[now][j][2]) {
                trans(nxt,j,1,'N',f[now][j][2]);
                trans(nxt,j,0,'O',f[now][j][2]);
            }
        }
    }
    for (int i=0;i<tot;++i)
        for (int j=0;j<3;++j)
            ans[popcount(i)]=(ans[popcount(i)]+f[n&1][i][j])%mod;
    for (int i=0;i<=k;++i) printf("%d\n",ans[i]);
    return 0;
}
最后修改：2020 年 06 月 07 日 05 : 16 PM
© 允许规范转载