Problem Link

题目大意

给定长度为 $n$ 的字符串 $S$，字符集 $\texttt {A,R,C}$，进行 $\le k$ 次操作得到 $T$：每次把一个长度为 $3$ 的子串替换成 $\texttt{ARC}$。

已知 $T$，求有多少个可能的 $S$。

数据范围：$n\le 5000,k\le 10^4$，

思路分析

时光倒流，一次操作会把 $T$ 中的 $\texttt{ARC}$ 子串变成三个任意字符，设为 $\texttt{???}$。

那么每次操作会把 $\texttt{ARC,AR?,A??,?RC,??C,?R?}$ 中的一个变成 $\texttt{???}$，这个过程中显然不可能产生 $\texttt{A?C}$。

考虑 $k=\infty$ 时怎么做，按 $\texttt{ARC,AR?,A??,?RC,??C,?R?}$ 的顺序把 $T$ 中若干元素变成 $\texttt{?}$，显然只有 $\texttt ?$ 上的元素能修改。

回到原问题，此时我们把 $T$ 分成若干 $\texttt{ARC,AR,A,RC,C,R,X}$ 子串（$\texttt X$ 表示未匹配字符），每个子串可以变成 $\texttt ?$ 但有些子串会依赖其前驱、后继。

考虑 dp，设 $f_{i,j,0/1}$ 表示决策了前 $i$ 个子串，最小操作次数为 $j$，是否钦定第 $i,i+1$ 个子串必须是 $\texttt ?$。

一个子串可以不变成 $\texttt ?$，不产生贡献，如果选择了变成 $\texttt ?$，就有 $3^{|o|}$ 贡献（其中 $o$ 是当前子串），有依赖关系的子串就会改变 $0/1$ 符号位。

但如果 $o$ 的前驱后继都不依赖 $o$，那么实际上没必要操作 $o$，因此我们钦定 $S$ 中的这个位置不等于 $o$，贡献变为 $3^{|o|}-1$。

时间复杂度 $\mathcal O(nk)$。

代码呈现

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=1e4+5,MOD=998244353,pw[]={1,3,9,27};
int n,m; string s;
ll f[MAXN][2];
struct info {
	int l,r;
	vector <string> q;
};
signed main() {
	ios::sync_with_stdio(false);
	cin>>s>>m,n=s.size();
	vector <info> Q;
	for(int i=0;i<n;++i) if(s.substr(i,3)=="ARC") {
		info o{i,i+3};
		while(true) {
			if(o.l>=1&&s.substr(o.l-1,1)=="A") o.q.push_back("A"),--o.l;
			else if(o.l>=2&&s.substr(o.l-2,2)=="AR") o.q.push_back("AR"),o.l-=2;
			else break;
		}
		reverse(o.q.begin(),o.q.end());
		o.q.push_back("ARC");
		while(true) {
			if(o.r<=n-1&&s.substr(o.r,1)=="C") o.q.push_back("C"),++o.r;
			else if(o.r<=n-2&&s.substr(o.r,2)=="RC") o.q.push_back("RC"),o.r+=2;
			else break;
		}
		Q.push_back(o);
	}
	vector <string> A;
	for(int i=0;i<(int)Q.size();++i) {
		if(i>=1) {
			A.push_back({Q[i-1].r+1==Q[i].l&&s[Q[i-1].r]=='R'?"R":" "});
		}
		A.insert(A.end(),Q[i].q.begin(),Q[i].q.end());
	}
	f[0][0]=1;
	for(auto o:A) {
		int w=pw[o.size()];
		for(int i=m-1;~i;--i) {
			if(o=="ARC") for(int x:{0,1}) for(int y:{0,1}) f[i+1][y]+=f[i][x]*(x||y?w:w-1);
			else if(o=="AR"||o=="A") for(int x:{0,1}) f[i+1][1]+=f[i][x]*(x?w:w-1);
			else if(o=="RC"||o=="C") for(int y:{0,1}) f[i+1][y]+=f[i][1]*(y?w:w-1);
			else if(o=="R") f[i+1][1]+=2*f[i][1];
			f[i][1]=0;
		}
		for(int i=0;i<=m;++i) for(int x:{0,1}) f[i][x]%=MOD;
	}
	ll ans=0;
	for(int i=0;i<=m;++i) ans=(ans+f[i][0])%MOD;
	cout<<ans<<"\n";
	return 0;
}