QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#19261 | #2398. ilove Strings | Qingyu | WA | 169ms | 390704kb | C++20 | 2.4kb | 2022-01-28 17:27:03 | 2022-05-06 04:33:37 |
Judging History
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);
}
详细
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'