自动搬运

查看原文

来自洛谷，原作者为

	wujingfey 我会像飞鸟一样死在天空中

搬运于2025-08-24 23:01:33，当前版本为作者最后更新于2024-09-29 22:03:48，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

传送门

所实话这题真的只有绿题难度吗？道心破碎了。

挑战本题最详细题解，求通过。

题意（人话版）

给你一个字符串 $s$，找其中一个长度为 $6$ 的序列满足ABCDCD形式的方案数，对 $998244353$ 取模。

$n\leqslant 10^6$

题解

观察ABCDCD的形式，可以把此题分成两部分考虑：AB+CDCD。详细地说，我们枚举每一位 $i$，分别求出 $[1,i-1]$ 中形如AB的方案数，然后在 $[i,len]$ 中求出形如CDCD的方案数。

对于前者

我们可以预处理：先开个桶 $t_{i,j}$ 表示前 $i$ 位，字符 $j$ 出现了多少次。再设 $g_{i}$ 表示前 $i$ 个字母能有多少种 AB 方案。

桶的转移很简单，就不细说了。考虑 $g$：每个 $g_i$ 从定义出发，就可以枚举每种字符出现的次数，然后乘以其他字符出现的次数：

for(int j=0;j<=61;j++){
	t[i][j]=t[i-1][j];//继承
	if(a[i]==j) t[i][j]++;//更新桶 
    g[i]+=t[i][j] * (i-t[i][j]);
	//枚举i,有i*(i-t[i][j])种AB方案 
}
g[i]>>=1;//AB、BA都会被计算，去除重复贡献

对于后者

我们从后往前枚举 $i$，维护CDCD方案数，同时记录答案。

记录CDCD的方案数，我们采用最朴素的“拼接法”。（设现在枚举到的字符是 $p$）。

• 如果我要知道 CDCD 的方案数，并且把 $p$ 固定成第一个 C，那么我们要在后面拼接 DCD。
• 如果我要知道后面 DCD 有多少种可行方案，我就要同时维护一个 DCD 的方案数。与上面类似，如果把 $p$ 固定成第一个 D，那我只需要再后面拼接 CD。
• 如果我要知道后面 CD 的方案数，同上，我需要记录 D 的方案数，也就是个桶了。

所以我用 $f1,f2,f3$ 分别记录：$p$ 固定成最后一个 D、最后一个 C、第一个 D 的方案数。

那么转移就不难想了。

• $f2$ 转移的时候，我们就是在 C 后面拼 D，那枚举所有可能的 D 加上贡献就好。
• $f3$ 转移也是同理，我们在第一个 D 后面拼接 CD，直接枚举每个 C，然后把 $f2$ 的方案数加在 $f3$ 上就好了。
• 现在知道了后面拼接 DCD 的方案数，第一个 C 也固定了，现在只需要解决前面 AB 的方案数就好。方案数已经预处理好了，现在只需要容斥掉 ABCD 出现相等的情况。
• 利用第一个桶中的信息和 $p$ 的位置，不难容斥出 AB 方案数。

for(int i=n;i>=1;i--){
	int p=a[i];
	f1[p]++;//f1记录D方案数 
	for(int j=0;j<=61;j++){
		//当前字母为p，也就是说：C固定为p，枚举所有CDC 
		if(j==p) continue;//重复不能计入 
		f3[p][j]+=f2[j][p], f3[p][j] %=mod;//f3记录DCD方案数 
		f2[p][j]+=f1[j], f2[p][j] %=mod;//f2记录CD方案数 
		//----------------------------容斥过程 
		int x1=t[i-1][j] * (i-1-t[i-1][j]) %mod;
		int x2=t[i-1][p] * (i-1-t[i-1][p]) %mod;
		int x3=t[i-1][j] * t[i-1][p] %mod;
		int x=(g[i-1] -x1 -x2 +x3 +mod) %mod;
		ans+=f3[j][p] * x, ans %= mod;
	}
}

两份核心代码加在一起就是 AC 代码了。

CODE：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+7,mod=998244353;
char s[N];
int n,ans,a[N],t[N][65];
int g[N],f1[65],f2[65][65],f3[65][65],f4[65][65];//dp数组 
void init(){//初始化 
	n=strlen(s+1);
	for(int i=1;i<=n;i++){
		if('A'<=s[i]&&s[i]<='Z') a[i]=s[i]-'A';
		else if('a'<=s[i]&&s[i]<='z') a[i]=s[i]-'a'+26;
		else a[i]=s[i]-'0'+52;
		for(int j=0;j<=61;j++){
			t[i][j]=t[i-1][j];//继承
			if(a[i]==j) t[i][j]++;//更新桶 
			g[i]+=t[i][j] * (i-t[i][j]);
			//枚举i,有i*(i-t[i][j])种AB方案 
		}
		g[i]>>=1;//AB、BA都会被计算，去除重复贡献 
	}
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>(s+1);
	init();
	for(int i=n;i>=1;i--){
		int p=a[i];
		f1[p]++;//f1记录D方案数 
		for(int j=0;j<=61;j++){
			//当前字母为p，也就是说：C固定位p，枚举所有CDC 
			if(j==p) continue;//重复不能计入 
			f3[p][j]+=f2[j][p], f3[p][j] %=mod;//f3记录DCD方案数 
			f2[p][j]+=f1[j], f2[p][j] %=mod;//f2记录CD方案数 
			//----------------------------容斥过程 
			int x1=t[i-1][j] * (i-1-t[i-1][j]) %mod;
			int x2=t[i-1][p] * (i-1-t[i-1][p]) %mod;
			int x3=t[i-1][j] * t[i-1][p] %mod;
			int x=(g[i-1] -x1 -x2 +x3 +mod) %mod;
			ans+=f3[j][p] * x, ans %= mod;
		}
	}
	cout<<ans;
	return 0;
}

这么好的题解真的不点个赞再走吗？