QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#211802 | #5051. Namomo Subsequence | bigJ | AC ✓ | 1133ms | 786116kb | C++20 | 1.9kb | 2023-10-12 21:23:11 | 2023-10-12 21:23:11 |
Judging History
answer
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxm=1e6+5;
const int mod=998244353;
char s[maxm];
int a[maxm];
int sum1[66][66];//AB的数量.
int sum2[66][66];//BAB的数量.
int cnt[66];
int f1[maxm][66];//[1,i]以Y结尾的XY数量.
int f2[maxm][66];//[1,i]以X开头的XY数量.
int cc[maxm][66];//[1,i]中X的数量.
int tot[maxm];//[1,i]中XY的总数量.
int n;
int cal(char c){
if(c>='0'&&c<='9')return c-'0';
else if(c>='a'&&c<='z')return c-'a'+10;
else return c-'A'+36;
}
inline void add(int &a,int b){
a+=b;
while(a>=mod)a-=mod;
while(a<0)a+=mod;
}
inline void DP(){
int ans=0;
for(int i=n;i>=3;i--){
for(int j=0;j<62;j++){
if(j==a[i])continue;
add(sum2[a[i]][j],sum1[j][a[i]]);
add(sum1[a[i]][j],cnt[j]);
}
cnt[a[i]]++;
for(int j=0;j<62;j++){
if(j==a[i])continue;
int temp=tot[i-1];
add(temp,-f1[i-1][a[i]]);
add(temp,-f1[i-1][j]);
add(temp,-f2[i-1][a[i]]);
add(temp,-f2[i-1][j]);
add(temp,1ll*cc[i-1][a[i]]*cc[i-1][j]%mod);
add(ans,1ll*sum2[j][a[i]]*temp%mod);
}
}
printf("%d\n",ans);
}
inline void solve(){
scanf("%s",s+1);
n=strlen(s+1);
for(int i=1;i<=n;i++)a[i]=cal(s[i]);
for(int i=1;i<=n;i++){
for(int j=0;j<62;j++){
cc[i][j]=cc[i-1][j];
f1[i][j]=f1[i-1][j];
f2[i][j]=f2[i-1][j];
}
cc[i][a[i]]++;
for(int j=0;j<62;j++){
if(j==a[i])continue;
add(f1[i][a[i]],cc[i-1][j]);
add(f2[i][j],cc[i-1][j]);
}
for(int j=0;j<62;j++){
add(tot[i],f1[i][j]);
}
}
DP();
}
signed main(){
solve();
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 5652kb
input:
wohaha
output:
1
result:
ok 1 number(s): "1"
Test #2:
score: 0
Accepted
time: 0ms
memory: 5768kb
input:
momomo
output:
0
result:
ok 1 number(s): "0"
Test #3:
score: 0
Accepted
time: 1ms
memory: 7680kb
input:
gshfd1jkhaRaadfglkjerVcvuy0gf
output:
73
result:
ok 1 number(s): "73"
Test #4:
score: 0
Accepted
time: 0ms
memory: 7708kb
input:
retiredMiFaFa0v0
output:
33
result:
ok 1 number(s): "33"
Test #5:
score: 0
Accepted
time: 670ms
memory: 786076kb
input:
bcdccccacccabdbdaddcabddbaccaaaaaabaccbbbcbbddabcbccabacdacbcbabccbcbddcdcbcaaadddddccdbabaabcbbcaaadadacdaadbdccbddddabcbaaddbcadadcbcbaaccacabdababaabdccadaddacdcacdaabbadadaddbbcccbcddaccaadbbcaaccccdcacbdbdddbaccaacbcaccaaabccdadddbaabdbcaaccacdcdcbcdddacbcacdbbbdccdddccccabdbacddacbaacbbcaccdcd...
output:
587599316
result:
ok 1 number(s): "587599316"
Test #6:
score: 0
Accepted
time: 695ms
memory: 785812kb
input:
cedcedaecbbcaceddaacaebeecdaceecdeeedaeebddbcabddeeeeaeeebcbcbabdaeeabddbcebecebaddadacedbacdabcedcecbecedacaedbdaaeaeedcbbcddbbbbdecbeedeadcbdacbeadcadaeeccbdeabedbabbbecbabaaeacdbcbbdedbaebaeadcdcacceeeccedcdcecdbcadcdecbdccadbdbdabbeacbaaacecbabdcecebecaebedcebcccacbcbcdcccdaaaaeacaabeedcbbbaeeea...
output:
604741630
result:
ok 1 number(s): "604741630"
Test #7:
score: 0
Accepted
time: 669ms
memory: 786080kb
input:
dcbbbdcafbfbcdbddfdebcebbfbedfafeadcceeafbdabbbfcefadaedbecbcfaeccdfddbfbeebceadcdeaaefcbecbaececdeddaeefdeaaeaecbdbececdadcacbbefdbbffddeefcecabbecafbbeaaeebedbeabbbaeabedaecffebfcbcfabedebcbadbbfbbebdfdaefcedbdeaacbebcdcbfbfdcabbcadddbdaeabbcdcdfbdfdbcaaaafbfdfabdcdeebcfebecdeacaddeebfecfccadcfdea...
output:
137937394
result:
ok 1 number(s): "137937394"
Test #8:
score: 0
Accepted
time: 712ms
memory: 785872kb
input:
bdfcdcegecbacccddgfdaddgaggefagabgggafgbaeaecgeacacgccadbfdebbdgbaffffgaegabeebacedabecgdfcbbfceeaecaaceebabddbfgefdabgbdbgggdgfegaadccdafgggeafdeecccaafgedfcbefdccafaaaafdcfaeagfeddggcfeeaacgaabadeegebfageeaaceaggddddfcggggdbeefeacdbafggffcdbcaacbaagbcceageaacedceeebacfebgceggffefgabgeaebacdbadcaeg...
output:
830637896
result:
ok 1 number(s): "830637896"
Test #9:
score: 0
Accepted
time: 678ms
memory: 786112kb
input:
bdceebdaahbcgefdbahfcaaaffhfcffgfbaefgehbefdgcgfcafbfdehdeccdbaacdffbhdhdfhdaeehfebgccghchdggcccdbafheaaadhefcbbdeddbfhaehddegcefebghgdahegfefeecbdacffaadbaehahcdbhcdfbacdgfefgeccfgbcbhdfggeecbggbhffceegaahfbahgdebfchhhddfhfcfcdfeddbcabggdfgacaeghechabbdaafbeehgaebfadfchahgdhgggfhehhcehedafhcfcgeegg...
output:
165134706
result:
ok 1 number(s): "165134706"
Test #10:
score: 0
Accepted
time: 726ms
memory: 786080kb
input:
gfgdeabdacecfgadbgbadgbhgafhfhdiageeefghgbhbfhhfaaideehaieaddhcabgdhidbdefeagdfchhccdabchhahgfddchdiegbhfdddefddbcaabhhhgghaafacbbbbaeagacbbdabdidibhgbihdahdeghaheedfechbhfbcabidafeccbcbfdcechdfddffbeagcegagfegdafeaabcafgbcfechhiaiechdhhfdcbceefbccdcadeachcffhaebhbiadgeeggfaeefiaecahdgfgaehcagaaffbc...
output:
729999334
result:
ok 1 number(s): "729999334"
Test #11:
score: 0
Accepted
time: 742ms
memory: 785900kb
input:
hcajfffideibggdfbdjjfbifgdcjibhdedgdibdgfjabaeijabebibcjfaddbiehadgggeadcaedieccdcgigccajjeicgbeijbahjjjghicaigiejgihiabeeggbfjdididdbggfcbhjajbjjgdabihijjddfhdhchggeegiecidjibdcccghfhcffcfehihdedgecbdfjjjiecedfhfjiefhjefbgbieeahcccfggcihbdbgjbdfhhbfghjeaijfagcgchaabijcdedjadfhgbgeefiijhhhcgfjeaadbe...
output:
342396794
result:
ok 1 number(s): "342396794"
Test #12:
score: 0
Accepted
time: 908ms
memory: 785944kb
input:
qsjdnlenipkknuvegwcozcrunnssjmuhdzvzocimsoqzdxsodpsfxhphbwgimyfzzuxowavmsncjjvxdksrambjzbuzkyqdbplbjxrdsacpgbiuzsalkytskdgsxcsblvzyvcgnieysbmeoyfaroxmuetwcvdkhyvlkwqdewldziradjmnkusdsrnybvhylzqroiblkloioqrtybukgmwwxqyjevkijesdddyjagspqqfdmkrhcnjaxcksolmetbutvcigrfhaghmjlzloqkxjooqutmejzhvpmmxzoupjoy...
output:
905453170
result:
ok 1 number(s): "905453170"
Test #13:
score: 0
Accepted
time: 916ms
memory: 785888kb
input:
antlkibnsqqmzaclyvinisylidtvoabqcndzhltrbohfqdfmdzzlyphhqhdbgdgcciyofikhxrqddkcenwhedsjbdwfqcdtrlmdpgpsbxebtwlucklnjqcbjeponmmxfbiuqwhtddfzfephrayohdqfkmzjtjqcywfkcvbtueapgzrlxoecguifcryoygybkkzjkpbmyscnfblbkcolqqeoffahxhbaupbzeazkjjwekeithdymqflpddwpwmpfsvlxwrwkpoetxuborumpzciuytnhgqqzfxbgrqjycqhkd...
output:
82912821
result:
ok 1 number(s): "82912821"
Test #14:
score: 0
Accepted
time: 881ms
memory: 786112kb
input:
khpwaiqnxudrpjjonholcibhhtuokklklxqlxtjzgtqekubgzwhznxzlbowxrseobjzswqvtcvlttnvyxaueqyferdhfbumuzobnmnmoxkkgnxhmykxezptnczshsotuqyqqfmwyuusowieyvskaagzcschzxasckzfezkznakkaeekgyumiabsjhkefbhyrrurqzjalbbecpiiyheqcxifnuwplabncdkweyuqbxhkecujztklbuegdseqzmevordemwmhysmtngpvfdsgskghujbnhkflycnwhbdiorbcw...
output:
659276694
result:
ok 1 number(s): "659276694"
Test #15:
score: 0
Accepted
time: 1065ms
memory: 785900kb
input:
yBsLfzzQCCwjLbfElpCOuMIyMwgSzrQLBnGYJWXFtobNLEGEYDOZUYKyviwbLelicegOrmebrrJkDDsyBDQiFxfHRecxeBUXZikRUctjMLaduPhhbMbgiQjRSrPkZuPoCTcmIrOwxhHTApmNTOwbSrSIKtxlSsVLOuLsfMDqpUHmVTyKzBdUVcJNJdLSDfTLFqVLCJEhkEOadDRRSRRNHefbsKopXMjAgTvXAAnByekMBgzgkbIwMKMeikEKfZzyqVoJVQevMNqXkfROFGjNBqZeDPDTVcTWnxckFdcOsMnj...
output:
916227453
result:
ok 1 number(s): "916227453"
Test #16:
score: 0
Accepted
time: 1110ms
memory: 786116kb
input:
mOGlQDSIpgfWtkiprbIfCGqllMlDEGeykbTgDFMsGSwTYsFcyWvFNkCgGTTXXTIUXrlSiYPWarEebKtOIvHmoljJaZehmSNVNJmqdaiWrRRQOTdNXSHNzYoQTxlaFoHEECYMQSNUnSOcShFbOMTCXdZWYbsNoQmpTouQkNwRlSTFdOBcxnrSXhayNLbScOQsvBZjQWfQSzFuVSyaAVwrTnwQDGvRYqXqyQsUYUPtMTrgVTPzsKhDfveExWfrRhqmqSvvwGbFuNdRSbUCwEiCjpEXPljvhJBMGJSwZBMWYpjc...
output:
205677196
result:
ok 1 number(s): "205677196"
Test #17:
score: 0
Accepted
time: 1133ms
memory: 785876kb
input:
fcD8e11SNuQ6pCULajtOr703RJpyQUDlmMcuP9L3rqRUi3NwKwxy7fnHb3d1RZdtnfFYvZEHJiQ1Woo6ThBnLxdtlBoLIMDvhZrXQTCHnAvnsNtaOfeDBzUZs2QcZstg7qEKo2WEBXAYa1FLLGMeoWfWhCDLE1eIZcepHViqkBXI5xoaUcf6RJApTzbYQnX1nIqkiGQjXUNlATaPByxRHo2ylfaqogW4c61wQVriSUhHerRQD9A3sbivWiJcwCbHpmpwBbmGkhrLYmV7xpwlwTUxgkRWCJ7DQFisYSxRv7QD...
output:
133494571
result:
ok 1 number(s): "133494571"
Test #18:
score: 0
Accepted
time: 1089ms
memory: 785872kb
input:
x4lsq2ZiboEadrneLYd1D3470OktjwPGpjdAtY2KaU2flHECAX68slVa68glymIhK54oblx8QPPRYp5o5k9We7vuCWYk35QHpw3JjkRalGZMN3tPK7MkXYlhrvAS725L7GGQcb4i6wL9Ew2KDxR1mcBAYSJTg7waIChN8q8My9Ifts43gdQGBxPY3PUGb2Motnyi7EMcdVsYbrxYa8RzSi55y84D7M7yWlnmkWnugPzhxgw0f5zCk0F7q4f5yz3jBnEkiInHGZM1a2aUavdOwBtz40XtqMt7eTSIB6hPfD2z...
output:
315491414
result:
ok 1 number(s): "315491414"