题解：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}

即可。

CPP

#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;
}

题解：AT_abc391_g [ABC391G] Many LCS

文章操作

相关推荐

评论

题解：AT_abc391_g [ABC391G] Many LCS