题解：AT_abc391_g [ABC391G] Many LCS

· · 题解

dp 套 dp 板子题。

考虑固定构成的字符串为 T 后，其与 S 的经典转移方程：

dp_{i,j}=\begin{cases} dp_{i-1,j-1}+1,s_i=t_j\\ \max(dp_{i,j-1},dp_{i-1,j}),s_i\neq t_j\end{cases}

考虑将其作为外层 dp 数组的一层状态，那么转移就相当于就是枚举当前加入哪一个字符，根据当前的字符来更新内层 dp 数组的状态。

将数组作为状态的一维显然不现实，将内层 dp 看作一个二维表格，每次在 T 后面添加字符相当于就是在这个表格内加一行或者一列。不妨钦定为列，那么当前列的值只会由上一列得到，并且发现对于一列而言，差分后的序列只会有 0 或者 1，于是就可以愉快状压了。

内层就是一个 DFA 转移的过程，预处理转移函数 nxt_{s,i} 即可。

#include<bits/stdc++.h>
using namespace std;
inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
    return x*f;
}
#define ll long long
const int mod=998244353;
const int maxn=1030;
ll t,n,m,nxt[maxn][27],dp[101][maxn],a[maxn],g[maxn],h[maxn],ans[maxn];
char s[20];
int main(){
    n=read(),m=read();
    cin>>(s+1);
    for(int i=1;i<=n;i++) a[i]=s[i]-'a';
    for(int s=0;s<(1<<n);s++){
        for(int i=1;i<=n;i++) g[i]=g[i-1]+((s>>(i-1))&1);
        for(int i=0;i<=25;i++){
            for(int j=1;j<=n;j++){
                if(i==a[j]) h[j]=g[j-1]+1;
                else h[j]=max(g[j],h[j-1]);
            }
            int now=0;
            for(int j=1;j<=n;j++) now+=((h[j]-h[j-1])<<(j-1));
            nxt[s][i]=now;
        }
    }
    dp[0][0]=1;
    for(int i=0;i<m;i++){
        for(int s=0;s<(1<<n);s++){
            for(int j=0;j<=25;j++) dp[i+1][nxt[s][j]]=(dp[i+1][nxt[s][j]]+dp[i][s])%mod;
        }
    }
    for(int i=0;i<(1<<n);i++) (ans[__builtin_popcount(i)]+=dp[m][i])%mod;
    for(int i=0;i<=n;i++) printf("%lld ",ans[i]%mod);
    return 0;
}