QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#19261#2398. ilove StringsQingyuWA 169ms390704kbC++202.4kb2022-01-28 17:27:032022-05-06 04:33:37

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-05-06 04:33:37]
  • 评测
  • 测评结果:WA
  • 用时:169ms
  • 内存:390704kb
  • [2022-01-28 17:27:03]
  • 提交

answer

#include <bits/stdc++.h>

const int N = 1e5 + 50;
const int CV = 11;
const int CC = 45;
const int mod = 1e9 + 7;

inline int inc(int x, int y) { x += y - mod; return x + (x >> 31 & mod); }
inline int dec(int x, int y) { x -= y; return x + (x >> 31 & mod); }
inline int mul(int x, int y) { return 1ll * x * y % mod; }

inline void upd(int &x, int y) { x = inc(x, y); }
inline void dpu(int &x, int y) { x = dec(x, y); }

int cur[CV][CC];
int pre[N][CV][CC], suf[N][CV][CC];
int n, map[255];
char s[N];

bool is_vowel(char ch) {
	ch = tolower(ch);
	return ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u';
}

bool is_consonant(char ch) {
	return !is_vowel(ch);
}

void init() {
	int total_vowels = 0, total_consonants = 0;
	memset(map, -1, sizeof map);
	for (char ch = 'a'; ch <= 'z'; ++ch)
		if (is_vowel(ch))
			map[ch] = ++total_vowels;
		else
			map[ch] = ++total_consonants;
	for (char ch = 'A'; ch <= 'Z'; ++ch)
		if (is_vowel(ch))
			map[ch] = ++total_vowels;
		else
			map[ch] = ++total_consonants;
	assert(total_vowels == 10 && total_consonants == 42);
}
//cur[CV][CC]
void add(char ch) {
	if (is_vowel(ch)) {
		++cur[map[ch]][0];
	}
	else {
		for (int i = 1; i <= 10; ++i) {
			upd(cur[i][map[ch]], cur[i][0]);
		}
	}
}

int pv[CV], sv[CV], pc[CC], sc[CC];

int main() {
	init();
	scanf("%s", s + 1);
	n = strlen(s + 1);
	memset(cur, 0, sizeof cur);
	cur[0][0] = 1;
	for (int i = 1; i <= n; ++i) {
		add(s[i]);
		memcpy(pre[i], cur, sizeof cur);
	}
	memset(cur, 0, sizeof cur);
	cur[0][0] = 1;
	for (int i = n; i >= 1; --i) {
		add(s[i]);
		memcpy(suf[i], cur, sizeof cur);
	}
	int ans = 0;
	for (int i = 1; i <= n; ++i) {
		if (is_vowel(s[i])) {
			int ps = 0, ss = 0;
			memset(pv, 0, sizeof pv);
			memset(pc, 0, sizeof pc);
			memset(sv, 0, sizeof sv);
			memset(sc, 0, sizeof sc);
			for (int a = 1; a <= 10; ++a)
				for (int b = 1; b <= 42; ++b) {
					upd(ps, pre[i - 1][a][b]);
					upd(ss, suf[i + 1][a][b]);
					upd(pv[a], pre[i - 1][a][b]);
					upd(pc[b], pre[i - 1][a][b]);
					upd(sv[a], suf[i + 1][a][b]);
					upd(sc[b], suf[i + 1][a][b]);
					upd(ans, mul(pre[i - 1][a][b], suf[i + 1][a][b]));
				}
			upd(ans, mul(ps, ss));
			for (int a = 1; a <= 10; ++a)
				dpu(ans, mul(pv[a], sv[a]));
			for (int a = 1; a <= 42; ++a)
				dpu(ans, mul(pc[a], sc[a]));
		
		}
	}
	printf("%d\n", ans);
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 3ms
memory: 5804kb

input:

ilovestrings

output:

4

result:

ok single line: '4'

Test #2:

score: 0
Accepted
time: 2ms
memory: 7892kb

input:

idont

output:

0

result:

ok single line: '0'

Test #3:

score: 0
Accepted
time: 3ms
memory: 5884kb

input:

CAPital

output:

1

result:

ok single line: '1'

Test #4:

score: 0
Accepted
time: 169ms
memory: 390688kb

input:

iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii...

output:

156800

result:

ok single line: '156800'

Test #5:

score: 0
Accepted
time: 160ms
memory: 390568kb

input:

yiyiyiyiyiyiyiyiyiyiyiyiyiyiyiyiyiyiyiyiyiyiyiyiyiyiyiyiyiyiyiyiyiyiyiyiyiyiyiyiyiyiyiyiyiyiyiyiyiyiyiyiyiyiyiyiyiyiyiyiyiyiyiyiyiyiyiyiyiyiyiyiyiyiyiyiyiyiyiyiyiyiyiyiyiyiyiyiyiyiyiyiyiyiyiyiyiyiyiyiyiyiyiyiyiyiyiyiyiyiyiyiyiyiyiyiyiyiyiyiyiyiyiyiyiyiyiyiyiyiyiyiyiyiyiyiyiyiyiyiyiyiyiyiyiyiyiyiyiyi...

output:

0

result:

ok single line: '0'

Test #6:

score: -100
Wrong Answer
time: 147ms
memory: 390704kb

input:

apadihijidunimizazawafemibibafuqoxiduxuyaguviredazesaqizoyekacatuzexuzehiyidupayigamazekofezawarolijozaqedizevepovofugopidequzixizexogirehurizodopaputudajatucopisemeforuhifafinovubexuseracejipamobajisokoqefajuhavexoqiwepumuyuyipiyiyaravorisicupawikewatexovowukutuwulusacukikebinojifupicopurexegosenic...

output:

767399436

result:

wrong answer 1st lines differ - expected: '276432330', found: '767399436'