统计 acgo 的出现次数 - 歪经题解

先看这题：P2646 数数zzy - 洛谷 | 计算机科学教育新生态
如果字符串出现了 y ，那么在它之前的 z 任意挑两个和这个 y 都可以组成一个 zzy 的子序列。
所以核心代码如下：

for(char c:s){
    if(c == 'z') ctz++;//记录z的数量
    if(c == 'y') ans += ctz * (ctz - 1) / 2;//挑两个z的组合数
}

这题同理，只不过复杂一些。

我们先记录 a 的数量。

如果一个字符是 c，那么在它之前所有的 a 与这个 c 都能组成一个 ac 的子序列，记录下来。

如果一个字符是 g，那么在它之前所有的 ac 与这个 g 都能组成一个 acg 的子序列，记录下来。

如果一个字符是 o，那么在它之前所有的 acg 与这个 o 都能组成一个 acgo 的子序列，记录下来。

答案就出来了！

#include <iostream>
#include <cstdio>
using namespace std;
int n;
string s;
struct modInt{//还是这个用着爽
	int val;
	void operator ++(int){
		val++;
		if(val == 998244353) val = 0;
	}
	void operator += (modInt b){
		val += b.val;
		if(val >= 998244353) val -= 998244353;
	}
}ct1, ct2, ct3, ct4;
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> n >> s;
	for(char i:s){
		if(i == 'a') ct1++;
		if(i == 'c') ct2 += ct1;
		if(i == 'g') ct3 += ct2;
		if(i == 'o') ct4 += ct3;//计算
	}
	cout << ct4.val;

	return 0;
}

时间复杂度：$O(N)$。