#C240929B. 串一串

标签（Label）

• 动态规划

网址（Website）

题目详情 - 串一串 - Super

题解 - 串一串 - Super

题解（Solution）

$\qquad$以下令 $n$ 表示字符串长度， $S$ 表示字符种类数。

$\qquad$很容易发现要求的是字符 $s$ 中 $abcdcd$ 形式的方案数。

$\qquad$单向求可以使用 $f[i][j][k][p][s]$ 表示字符为 ijkp ， $s=0，1，2$ ，分别指 ijkp、ijkpk、ijkpkp 六种状态，最后要计算的答案就是 $\sum f[i][j][k][p][2]$ ，时间复杂度 $O(nS^3)$ 。

$\qquad$考虑寻找中间量，发现可以在 $O(nS)$ 的时间内处理出 $ab$ 形式的字符的方案数，令 $t[i][c]$ 表示 $1\sim i$ 字符为 $c$ 的个数，$tt[i][c]$ 为到 $i$ 为止形如 cc 的方案数， $tc[i]$ 表示 $1\sim i$ 总共的方案数。我们钦定第一个 $c$ 为中间的计算量，倒序枚举 $s$ ，令 $r1[i][j]$ 表示形如 iji 的方案数， $r2[i][j]$ 表示形如 ij 的方案数，推得方程后计算答案即可。

出题者题解

题目即为求形如 ABCDCD 的子序列数量。倒序枚举 C 的位置以及字符 D、DCD 的数量可以 DP 求出，AB 的数量可以通过预处理每个前缀的每种字符出现次数 $cnt_c$ 以及 $\sum C_{cnt_c}^{2}$ 的值求出。时间复杂度 $O(64n)$ （ $n$ 为长度）。

代码（Code）

#include<bits/stdc++.h>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define Rof(i,l,r) for(int i=l;i>=r;i--)
using namespace std;
#define P pair<int,int>
#define int long long
#define ull long long
#define x first
#define y second
inline int rd(){
	char c;bool f=false;while(!isdigit(c=getchar()))f=c=='-';int x=c^48;
	while(isdigit(c=getchar())){x=(((x<<2)+x)<<1)+(c^48);}return f?-x:x;
}const int inf = 0x3f3f3f3f;
const int mod = 998244353;
const int N = 1e6+5;
const int B = 63;
bool ST;

int n,c[N],ans;
char s[N];

inline void add(int &x,int y){if((x+=y)>mod)x-=mod;}
inline void sub(int &x,int y){if((x-=y)<0)x+=mod;}
inline int cal(int x){return (ull)x*(x-1)/2%mod;}

int t[N][B],tt[N][B],tc[N];
int r1[B][B],r2[B][B];
inline void Solve(){
	n = strlen(s+1);
	For(i,1,n){
		if(isdigit(s[i])) c[i]=s[i]-'0'+1;else
		if(islower(s[i])) c[i]=s[i]-'a'+11;else
		if(isupper(s[i])) c[i]=s[i]-'A'+37;
		else cout<<"WA\n",exit(0);
		For(j,1,62){
			t[i][j] = t[i-1][j] + (j==c[i]);
			tt[i][j] = cal(t[i][j]);//a和a匹配的方案数 
			add(tc[i], tt[i][j]);//到i为止总共的方案数 
		}
	}
	Rof(i,n,3){//前面至少要有ab 
		For(j,1,62){
			if(c[i]==j) continue;//如果重复了，跳过
			int tmp = (i-1) - t[i-1][c[i]] - t[i-1][j];//前面没有这两个字符的方案数 
			int lft = ((ull)cal(tmp) - tc[i-1] + tt[i-1][j] + tt[i-1][c[i]] + mod)%mod;
			add(ans, (ull)lft*r1[j][c[i]]%mod);
			add(r1[c[i]][j],r2[j][c[i]]);
			add(r2[c[i]][j],t[n][j]-t[i][j]);
		}
	}
}

bool ED;
signed main(){
	cerr<<abs(&ST-&ED)/1024./1024.<<"MB\n";
	freopen("string.in","r",stdin);
	freopen("string.out","w",stdout);
	scanf("%s",s+1);int Tim = clock();
	Solve(),printf("%lld\n",ans%mod);
	return cerr<<"TIME:"<<(clock()-Tim)/1000.,0;
}