[AtCoder] [經典競程 90 題] 008 - AtCounter(★4)

題目連結:https://atcoder.jp/contests/typical90/tasks/typical90_h 題目大意:
給定一個字串 $S$ ,問其中有多少子字串 "atcoder"。
由左往右暴力掃一遍維護一下當下有多少 a, at, atc, atco, atcod, atcode, atcoder 就好ㄌ
#include <bits/stdc++.h>
using namespace std;
const int MOD = 1'000'000'007;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	int n; cin >> n;
	string s; cin >> s;
	int ca = 0, cat = 0, catc = 0, catco = 0, catcod = 0, catcode = 0, catcoder = 0;
	for (auto c: s) {
		switch (c) {
			case 'a':
				ca++;
				break;
			case 't':
				cat+=ca;
				cat%=MOD;
				break;
			case 'c':
				catc+=cat;
				catc%=MOD;
				break;
			case 'o':
				catco+=catc;
				catco%=MOD;
				break;
			case 'd':
				catcod+=catco;
				catcod%=MOD;
				break;
			case 'e':
				catcode+=catcod;
				catcode%=MOD;
				break;
			case 'r':
				catcoder+=catcode;
				catcoder%=MOD;
				break;
		}
	}
	cout << catcoder << '\n';
	return 0;
} 

留言

這個網誌中的熱門文章

[TIOJ] 1271. [IOI 2012] Scrivener 斯克里夫尼

[TIOJ] 1429. [APIO '12] 忍者調度問題

[Codeforces] 731D. 80-th Level Archeology