QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#793840 | #5051. Namomo Subsequence | LJY_ljy | TL | 2713ms | 835040kb | C++14 | 3.6kb | 2024-11-30 02:24:41 | 2024-11-30 02:24:45 |
Judging History
answer
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <string>
#include <vector>
using namespace std;
const long long MOD = 998244353;
const long long MAXN = 1e6 + 10;
const long long MAXM = 65; // 'a' - 'z', 'A' - 'Z', '0' - '9'
char str[MAXN];
int cnt[MAXN][MAXM];
long long Sum[MAXN];
vector<int> Index[MAXM];
vector<int> sum[MAXM][MAXM];
vector<int> cnt2[MAXM], cnt3[MAXM][MAXM];
long long Tran(char c) {
if ('a' <= c && c <= 'z') return c - 'a' + 1;
if ('A' <= c && c <= 'Z') return c - 'A' + 27;
return c - '0' + 53;
}
int main() {
scanf("%s", str + 1);
long long n = strlen(str + 1);
for (long long i = 1; i <= n; i++) {
for (long long j = 1; j <= 62; j++)
cnt[i][j] = cnt[i - 1][j];
cnt[i][Tran(str[i])] = cnt[i - 1][Tran(str[i])] + 1;
Index[Tran(str[i])].push_back(i);
Sum[i] = ( Sum[i - 1] + (1ll * cnt[i][Tran(str[i])] * (cnt[i][Tran(str[i])] - 1) / 2) % MOD - (1ll * (cnt[i][Tran(str[i])] - 1) * (cnt[i][Tran(str[i])] - 2) / 2) % MOD + MOD) % MOD;
}
for (long long i = 1; i <= 62; i++) {
long long A = 0;
for (long long j = 0; j < Index[i].size(); j++) {
A = (A + Index[i][j]) % MOD;
cnt2[i].push_back(A);
}
}
// for (long long u = 1; u <= 62; u++) {
// for (long long i = 1; i <= 62; i++) {
// long long A = 0;
// for (long long j = 0; j < Index[i].size(); j++) {
// A = (A + cnt[Index[i][j]][u]) % MOD;
// cnt3[i][u].push_back(A);
// }
// }
// }
for (long long i = 1; i <= 62; i++) { // C
for (long long u = 1; u <= 62; u++) { // D
long long ans = 0, Sumsum = 0;
if (!Index[u].empty()) {
cnt3[u][i].push_back(0);
for (long long x = Index[u].size() - 1; x >= 0; x--) {
ans = (ans + cnt[Index[u][x]][i]) % MOD;
cnt3[u][i].push_back(ans);
Sumsum = (Sumsum + ( ans - ( 1ll * (Index[u].size() - x) * cnt[Index[u][x]][i]) % MOD + MOD) % MOD) % MOD;
sum[u][i].push_back(Sumsum);
}
}
}
}
long long Cnt = 0;
for (long long i = 1; i <= 62; i++) {
for (long long j = 0; j < Index[i].size(); j++) {
long long I = 1ll * Index[i][j];
long long ans1 = ( ( (I - 1) * (I - 2) / 2) % MOD - Sum[I - 1] + MOD) % MOD; // ABC
long long ans2 = 0, ans3 = 0;
if (j > 0) {
ans2 = (cnt2[i][j - 1] - (cnt3[i][i][Index[i].size()] - cnt3[i][i][Index[i].size() - j] + MOD) % MOD + MOD) % MOD; //XCC;
ans3 = ( (1ll * j * I) % MOD - cnt2[i][j - 1] + 2 * MOD - (1ll * j * j) % MOD + (1ll * (j - 1) * j / 2) % MOD + MOD) % MOD; //CXC
}
long long A = (ans1 - ans2 - ans3 + 2 * MOD) % MOD; // ABC
for (long long u = 1; u <= 62; u++) {
if (u != i) {
long long ans5 = 0, ans6 = 0;
if (cnt[I][u] >= 1) {
ans5 = (cnt2[u][cnt[I][u] - 1] - (cnt3[u][i][Index[u].size()] - cnt3[u][i][Index[u].size() - cnt[I][u]] + MOD) % MOD - (cnt3[u][u][Index[u].size()] - cnt3[u][u][Index[u].size() - cnt[I][u]] + MOD) % MOD + 2 * MOD) % MOD; // XDC
ans6 = ((1ll * cnt[I][u] * I) % MOD - cnt2[u][cnt[I][u] - 1] - cnt[I][u] + 2 * MOD) % MOD; //DXC, X任意
long long ans7 = ((1ll * cnt[I][u]) * (1ll * (cnt[I][u] - 1)) / 2) % MOD; // DDC
long long ans8 = 0;
if (j >= 1)
ans8 = (cnt3[i][u][Index[i].size()] - cnt3[i][u][Index[i].size() - j] + MOD) % MOD; //DCC
ans6 = (ans6 - ans7 - ans8 + 2 * MOD) % MOD;
}
long long B = (A - ans5 - ans6 + 2 * MOD) % MOD;
if (cnt[n][u] != cnt[I][u]) {
//cout << B << " " << sum[u][i][cnt[n][u] - cnt[I][u] - 1] << endl;
Cnt = ( Cnt + (1ll * B * sum[u][i][cnt[n][u] - cnt[I][u] - 1]) % MOD ) % MOD;
}
}
}
}
}
printf("%lld\n", Cnt);
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 4108kb
input:
wohaha
output:
1
result:
ok 1 number(s): "1"
Test #2:
score: 0
Accepted
time: 1ms
memory: 4080kb
input:
momomo
output:
0
result:
ok 1 number(s): "0"
Test #3:
score: 0
Accepted
time: 0ms
memory: 8132kb
input:
gshfd1jkhaRaadfglkjerVcvuy0gf
output:
73
result:
ok 1 number(s): "73"
Test #4:
score: 0
Accepted
time: 1ms
memory: 4120kb
input:
retiredMiFaFa0v0
output:
33
result:
ok 1 number(s): "33"
Test #5:
score: 0
Accepted
time: 2644ms
memory: 760176kb
input:
bcdccccacccabdbdaddcabddbaccaaaaaabaccbbbcbbddabcbccabacdacbcbabccbcbddcdcbcaaadddddccdbabaabcbbcaaadadacdaadbdccbddddabcbaaddbcadadcbcbaaccacabdababaabdccadaddacdcacdaabbadadaddbbcccbcddaccaadbbcaaccccdcacbdbdddbaccaacbcaccaaabccdadddbaabdbcaaccacdcdcbcdddacbcacdbbbdccdddccccabdbacddacbaacbbcaccdcd...
output:
587599316
result:
ok 1 number(s): "587599316"
Test #6:
score: 0
Accepted
time: 2493ms
memory: 760424kb
input:
cedcedaecbbcaceddaacaebeecdaceecdeeedaeebddbcabddeeeeaeeebcbcbabdaeeabddbcebecebaddadacedbacdabcedcecbecedacaedbdaaeaeedcbbcddbbbbdecbeedeadcbdacbeadcadaeeccbdeabedbabbbecbabaaeacdbcbbdedbaebaeadcdcacceeeccedcdcecdbcadcdecbdccadbdbdabbeacbaaacecbabdcecebecaebedcebcccacbcbcdcccdaaaaeacaabeedcbbbaeeea...
output:
604741630
result:
ok 1 number(s): "604741630"
Test #7:
score: 0
Accepted
time: 2584ms
memory: 760632kb
input:
dcbbbdcafbfbcdbddfdebcebbfbedfafeadcceeafbdabbbfcefadaedbecbcfaeccdfddbfbeebceadcdeaaefcbecbaececdeddaeefdeaaeaecbdbececdadcacbbefdbbffddeefcecabbecafbbeaaeebedbeabbbaeabedaecffebfcbcfabedebcbadbbfbbebdfdaefcedbdeaacbebcdcbfbfdcabbcadddbdaeabbcdcdfbdfdbcaaaafbfdfabdcdeebcfebecdeacaddeebfecfccadcfdea...
output:
137937394
result:
ok 1 number(s): "137937394"
Test #8:
score: 0
Accepted
time: 2504ms
memory: 761244kb
input:
bdfcdcegecbacccddgfdaddgaggefagabgggafgbaeaecgeacacgccadbfdebbdgbaffffgaegabeebacedabecgdfcbbfceeaecaaceebabddbfgefdabgbdbgggdgfegaadccdafgggeafdeecccaafgedfcbefdccafaaaafdcfaeagfeddggcfeeaacgaabadeegebfageeaaceaggddddfcggggdbeefeacdbafggffcdbcaacbaagbcceageaacedceeebacfebgceggffefgabgeaebacdbadcaeg...
output:
830637896
result:
ok 1 number(s): "830637896"
Test #9:
score: 0
Accepted
time: 2688ms
memory: 772128kb
input:
bdceebdaahbcgefdbahfcaaaffhfcffgfbaefgehbefdgcgfcafbfdehdeccdbaacdffbhdhdfhdaeehfebgccghchdggcccdbafheaaadhefcbbdeddbfhaehddegcefebghgdahegfefeecbdacffaadbaehahcdbhcdfbacdgfefgeccfgbcbhdfggeecbggbhffceegaahfbahgdebfchhhddfhfcfcdfeddbcabggdfgacaeghechabbdaafbeehgaebfadfchahgdhgggfhehhcehedafhcfcgeegg...
output:
165134706
result:
ok 1 number(s): "165134706"
Test #10:
score: 0
Accepted
time: 2672ms
memory: 803272kb
input:
gfgdeabdacecfgadbgbadgbhgafhfhdiageeefghgbhbfhhfaaideehaieaddhcabgdhidbdefeagdfchhccdabchhahgfddchdiegbhfdddefddbcaabhhhgghaafacbbbbaeagacbbdabdidibhgbihdahdeghaheedfechbhfbcabidafeccbcbfdcechdfddffbeagcegagfegdafeaabcafgbcfechhiaiechdhhfdcbceefbccdcadeachcffhaebhbiadgeeggfaeefiaecahdgfgaehcagaaffbc...
output:
729999334
result:
ok 1 number(s): "729999334"
Test #11:
score: 0
Accepted
time: 2713ms
memory: 835040kb
input:
hcajfffideibggdfbdjjfbifgdcjibhdedgdibdgfjabaeijabebibcjfaddbiehadgggeadcaedieccdcgigccajjeicgbeijbahjjjghicaigiejgihiabeeggbfjdididdbggfcbhjajbjjgdabihijjddfhdhchggeegiecidjibdcccghfhcffcfehihdedgecbdfjjjiecedfhfjiefhjefbgbieeahcccfggcihbdbgjbdfhhbfghjeaijfagcgchaabijcdedjadfhgbgeefiijhhhcgfjeaadbe...
output:
342396794
result:
ok 1 number(s): "342396794"
Test #12:
score: -100
Time Limit Exceeded
input:
qsjdnlenipkknuvegwcozcrunnssjmuhdzvzocimsoqzdxsodpsfxhphbwgimyfzzuxowavmsncjjvxdksrambjzbuzkyqdbplbjxrdsacpgbiuzsalkytskdgsxcsblvzyvcgnieysbmeoyfaroxmuetwcvdkhyvlkwqdewldziradjmnkusdsrnybvhylzqroiblkloioqrtybukgmwwxqyjevkijesdddyjagspqqfdmkrhcnjaxcksolmetbutvcigrfhaghmjlzloqkxjooqutmejzhvpmmxzoupjoy...