QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#687262 | #5051. Namomo Subsequence | Repeater | AC ✓ | 360ms | 4304kb | C++20 | 1.4kb | 2024-10-29 17:53:45 | 2024-10-29 17:53:46 |
Judging History
answer
#include <bits/stdc++.h>
using i64 = long long;
constexpr int P = 998244353;
constexpr int M = 62;
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::string s; std::cin >> s;
int n = s.size();
std::vector<i64> cnt(M);
i64 sum = 0, sum2 = 0;
auto trans = [&](char c) -> int
{
if('a' <= c && c <= 'z') return (c - 'a');
if('A' <= c && c <= 'Z') return 26 + (c - 'A');
if('0' <= c && c <= '9') return 52 + (c - '0');
return -1;
};
auto plus = [&](i64 &a, i64 b) -> void
{
a += b;
if(a >= P) a -= P;
};
auto add = [&](int x) -> void
{
sum++;
cnt[x]++;
sum2 += 2 * cnt[x] - 1;
};
auto del = [&](int x) -> void
{
sum--;
sum2 -= 2 * cnt[x] - 1;
cnt[x]--;
};
auto query = [&](int x, int y) -> i64
{
return ((sum - cnt[x] - cnt[y]) * (sum - cnt[x] - cnt[y]) - (sum2 - cnt[x] * cnt[x] - cnt[y] * cnt[y])) / 2 % P;
};
for(auto c : s) add(trans(c));
std::vector f(4, std::vector(M, std::vector<i64>(M)));
for(int i = 0; i < M; i++)
for(int j = 0; j < M; j++)
if(i != j) f[0][i][j] = 1;
i64 ans = 0;
for(auto c : std::views::reverse(s))
{
int t = trans(c);
del(t);
for(int j = 0; j < M; j++) if(j != t)
{
plus(f[1][j][t], f[0][j][t]);
plus(f[2][t][j], f[1][t][j]);
plus(f[3][j][t], f[2][j][t]);
ans = (ans + f[3][t][j] * query(t, j)) % P;
}
}
std::cout << ans << "\n";
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3788kb
input:
wohaha
output:
1
result:
ok 1 number(s): "1"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3968kb
input:
momomo
output:
0
result:
ok 1 number(s): "0"
Test #3:
score: 0
Accepted
time: 0ms
memory: 3788kb
input:
gshfd1jkhaRaadfglkjerVcvuy0gf
output:
73
result:
ok 1 number(s): "73"
Test #4:
score: 0
Accepted
time: 0ms
memory: 3936kb
input:
retiredMiFaFa0v0
output:
33
result:
ok 1 number(s): "33"
Test #5:
score: 0
Accepted
time: 336ms
memory: 4160kb
input:
bcdccccacccabdbdaddcabddbaccaaaaaabaccbbbcbbddabcbccabacdacbcbabccbcbddcdcbcaaadddddccdbabaabcbbcaaadadacdaadbdccbddddabcbaaddbcadadcbcbaaccacabdababaabdccadaddacdcacdaabbadadaddbbcccbcddaccaadbbcaaccccdcacbdbdddbaccaacbcaccaaabccdadddbaabdbcaaccacdcdcbcdddacbcacdbbbdccdddccccabdbacddacbaacbbcaccdcd...
output:
587599316
result:
ok 1 number(s): "587599316"
Test #6:
score: 0
Accepted
time: 345ms
memory: 4176kb
input:
cedcedaecbbcaceddaacaebeecdaceecdeeedaeebddbcabddeeeeaeeebcbcbabdaeeabddbcebecebaddadacedbacdabcedcecbecedacaedbdaaeaeedcbbcddbbbbdecbeedeadcbdacbeadcadaeeccbdeabedbabbbecbabaaeacdbcbbdedbaebaeadcdcacceeeccedcdcecdbcadcdecbdccadbdbdabbeacbaaacecbabdcecebecaebedcebcccacbcbcdcccdaaaaeacaabeedcbbbaeeea...
output:
604741630
result:
ok 1 number(s): "604741630"
Test #7:
score: 0
Accepted
time: 351ms
memory: 4176kb
input:
dcbbbdcafbfbcdbddfdebcebbfbedfafeadcceeafbdabbbfcefadaedbecbcfaeccdfddbfbeebceadcdeaaefcbecbaececdeddaeefdeaaeaecbdbececdadcacbbefdbbffddeefcecabbecafbbeaaeebedbeabbbaeabedaecffebfcbcfabedebcbadbbfbbebdfdaefcedbdeaacbebcdcbfbfdcabbcadddbdaeabbcdcdfbdfdbcaaaafbfdfabdcdeebcfebecdeacaddeebfecfccadcfdea...
output:
137937394
result:
ok 1 number(s): "137937394"
Test #8:
score: 0
Accepted
time: 349ms
memory: 4128kb
input:
bdfcdcegecbacccddgfdaddgaggefagabgggafgbaeaecgeacacgccadbfdebbdgbaffffgaegabeebacedabecgdfcbbfceeaecaaceebabddbfgefdabgbdbgggdgfegaadccdafgggeafdeecccaafgedfcbefdccafaaaafdcfaeagfeddggcfeeaacgaabadeegebfageeaaceaggddddfcggggdbeefeacdbafggffcdbcaacbaagbcceageaacedceeebacfebgceggffefgabgeaebacdbadcaeg...
output:
830637896
result:
ok 1 number(s): "830637896"
Test #9:
score: 0
Accepted
time: 345ms
memory: 4152kb
input:
bdceebdaahbcgefdbahfcaaaffhfcffgfbaefgehbefdgcgfcafbfdehdeccdbaacdffbhdhdfhdaeehfebgccghchdggcccdbafheaaadhefcbbdeddbfhaehddegcefebghgdahegfefeecbdacffaadbaehahcdbhcdfbacdgfefgeccfgbcbhdfggeecbggbhffceegaahfbahgdebfchhhddfhfcfcdfeddbcabggdfgacaeghechabbdaafbeehgaebfadfchahgdhgggfhehhcehedafhcfcgeegg...
output:
165134706
result:
ok 1 number(s): "165134706"
Test #10:
score: 0
Accepted
time: 356ms
memory: 4148kb
input:
gfgdeabdacecfgadbgbadgbhgafhfhdiageeefghgbhbfhhfaaideehaieaddhcabgdhidbdefeagdfchhccdabchhahgfddchdiegbhfdddefddbcaabhhhgghaafacbbbbaeagacbbdabdidibhgbihdahdeghaheedfechbhfbcabidafeccbcbfdcechdfddffbeagcegagfegdafeaabcafgbcfechhiaiechdhhfdcbceefbccdcadeachcffhaebhbiadgeeggfaeefiaecahdgfgaehcagaaffbc...
output:
729999334
result:
ok 1 number(s): "729999334"
Test #11:
score: 0
Accepted
time: 350ms
memory: 4176kb
input:
hcajfffideibggdfbdjjfbifgdcjibhdedgdibdgfjabaeijabebibcjfaddbiehadgggeadcaedieccdcgigccajjeicgbeijbahjjjghicaigiejgihiabeeggbfjdididdbggfcbhjajbjjgdabihijjddfhdhchggeegiecidjibdcccghfhcffcfehihdedgecbdfjjjiecedfhfjiefhjefbgbieeahcccfggcihbdbgjbdfhhbfghjeaijfagcgchaabijcdedjadfhgbgeefiijhhhcgfjeaadbe...
output:
342396794
result:
ok 1 number(s): "342396794"
Test #12:
score: 0
Accepted
time: 347ms
memory: 4172kb
input:
qsjdnlenipkknuvegwcozcrunnssjmuhdzvzocimsoqzdxsodpsfxhphbwgimyfzzuxowavmsncjjvxdksrambjzbuzkyqdbplbjxrdsacpgbiuzsalkytskdgsxcsblvzyvcgnieysbmeoyfaroxmuetwcvdkhyvlkwqdewldziradjmnkusdsrnybvhylzqroiblkloioqrtybukgmwwxqyjevkijesdddyjagspqqfdmkrhcnjaxcksolmetbutvcigrfhaghmjlzloqkxjooqutmejzhvpmmxzoupjoy...
output:
905453170
result:
ok 1 number(s): "905453170"
Test #13:
score: 0
Accepted
time: 350ms
memory: 4304kb
input:
antlkibnsqqmzaclyvinisylidtvoabqcndzhltrbohfqdfmdzzlyphhqhdbgdgcciyofikhxrqddkcenwhedsjbdwfqcdtrlmdpgpsbxebtwlucklnjqcbjeponmmxfbiuqwhtddfzfephrayohdqfkmzjtjqcywfkcvbtueapgzrlxoecguifcryoygybkkzjkpbmyscnfblbkcolqqeoffahxhbaupbzeazkjjwekeithdymqflpddwpwmpfsvlxwrwkpoetxuborumpzciuytnhgqqzfxbgrqjycqhkd...
output:
82912821
result:
ok 1 number(s): "82912821"
Test #14:
score: 0
Accepted
time: 350ms
memory: 4204kb
input:
khpwaiqnxudrpjjonholcibhhtuokklklxqlxtjzgtqekubgzwhznxzlbowxrseobjzswqvtcvlttnvyxaueqyferdhfbumuzobnmnmoxkkgnxhmykxezptnczshsotuqyqqfmwyuusowieyvskaagzcschzxasckzfezkznakkaeekgyumiabsjhkefbhyrrurqzjalbbecpiiyheqcxifnuwplabncdkweyuqbxhkecujztklbuegdseqzmevordemwmhysmtngpvfdsgskghujbnhkflycnwhbdiorbcw...
output:
659276694
result:
ok 1 number(s): "659276694"
Test #15:
score: 0
Accepted
time: 359ms
memory: 4096kb
input:
yBsLfzzQCCwjLbfElpCOuMIyMwgSzrQLBnGYJWXFtobNLEGEYDOZUYKyviwbLelicegOrmebrrJkDDsyBDQiFxfHRecxeBUXZikRUctjMLaduPhhbMbgiQjRSrPkZuPoCTcmIrOwxhHTApmNTOwbSrSIKtxlSsVLOuLsfMDqpUHmVTyKzBdUVcJNJdLSDfTLFqVLCJEhkEOadDRRSRRNHefbsKopXMjAgTvXAAnByekMBgzgkbIwMKMeikEKfZzyqVoJVQevMNqXkfROFGjNBqZeDPDTVcTWnxckFdcOsMnj...
output:
916227453
result:
ok 1 number(s): "916227453"
Test #16:
score: 0
Accepted
time: 356ms
memory: 4148kb
input:
mOGlQDSIpgfWtkiprbIfCGqllMlDEGeykbTgDFMsGSwTYsFcyWvFNkCgGTTXXTIUXrlSiYPWarEebKtOIvHmoljJaZehmSNVNJmqdaiWrRRQOTdNXSHNzYoQTxlaFoHEECYMQSNUnSOcShFbOMTCXdZWYbsNoQmpTouQkNwRlSTFdOBcxnrSXhayNLbScOQsvBZjQWfQSzFuVSyaAVwrTnwQDGvRYqXqyQsUYUPtMTrgVTPzsKhDfveExWfrRhqmqSvvwGbFuNdRSbUCwEiCjpEXPljvhJBMGJSwZBMWYpjc...
output:
205677196
result:
ok 1 number(s): "205677196"
Test #17:
score: 0
Accepted
time: 359ms
memory: 4300kb
input:
fcD8e11SNuQ6pCULajtOr703RJpyQUDlmMcuP9L3rqRUi3NwKwxy7fnHb3d1RZdtnfFYvZEHJiQ1Woo6ThBnLxdtlBoLIMDvhZrXQTCHnAvnsNtaOfeDBzUZs2QcZstg7qEKo2WEBXAYa1FLLGMeoWfWhCDLE1eIZcepHViqkBXI5xoaUcf6RJApTzbYQnX1nIqkiGQjXUNlATaPByxRHo2ylfaqogW4c61wQVriSUhHerRQD9A3sbivWiJcwCbHpmpwBbmGkhrLYmV7xpwlwTUxgkRWCJ7DQFisYSxRv7QD...
output:
133494571
result:
ok 1 number(s): "133494571"
Test #18:
score: 0
Accepted
time: 360ms
memory: 4180kb
input:
x4lsq2ZiboEadrneLYd1D3470OktjwPGpjdAtY2KaU2flHECAX68slVa68glymIhK54oblx8QPPRYp5o5k9We7vuCWYk35QHpw3JjkRalGZMN3tPK7MkXYlhrvAS725L7GGQcb4i6wL9Ew2KDxR1mcBAYSJTg7waIChN8q8My9Ifts43gdQGBxPY3PUGb2Motnyi7EMcdVsYbrxYa8RzSi55y84D7M7yWlnmkWnugPzhxgw0f5zCk0F7q4f5yz3jBnEkiInHGZM1a2aUavdOwBtz40XtqMt7eTSIB6hPfD2z...
output:
315491414
result:
ok 1 number(s): "315491414"