QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#573225 | #5051. Namomo Subsequence | confirm14478 | AC ✓ | 2368ms | 59076kb | C++14 | 3.4kb | 2024-09-18 17:48:45 | 2024-09-18 17:48:45 |
Judging History
answer
#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
#define int long long
#define YES cout<<"YES\n"
#define NO cout<<"NO\n"
#define endl "\n"
#define debug cout<<'*'<<'\n'
const int N = 1e6 + 50, M = 70;
const int mod = 998244353, inf = 0x3f3f3f3f3f3f3f3f;
using namespace std;
int to_int(char c) {
if(c<='z'&c>='a')return c-'a'+1;
else if(c<='Z'&&c>='A')return c-'A'+27;
else return c-'0'+53;
}
int a[N];
vector<int> inv[N];
int pre[N],hs[M];
void solve()
{
string s;
cin>>s;
int n = s.size(),m = 62;
s=' '+s;
for(int i=1;i<=n;i++) a[i]=to_int(s[i]);
for(int i=1;i<=n;i++) inv[a[i]].push_back(i);
for(int i=1;i<=n;i++) {
hs[a[i]]++;
pre[i]=(pre[i-1]+(i-hs[a[i]]))%mod;
}
//for(int i=1;i<=n;i++)cout<<pre[i]<<" ";cout<<endl;
int ans=0;
for(int i=1;i<=m;i++) {
for(int j=i+1;j<=m;j++) {
int si=inv[i].size(),sj=inv[j].size();
int p[si+sj+1];
int cnti=0,cntj=0,cnt=0;
while(cnti<si&&cntj<sj) {
if(inv[i][cnti]<inv[j][cntj])p[++cnt]=inv[i][cnti++];
else p[++cnt]=inv[j][cntj++];
}
while(cnti<si)p[++cnt]=inv[i][cnti++];
while(cntj<sj)p[++cnt]=inv[j][cntj++];
if(cnti==0||cntj==0)continue;;
//cout<<i<<" - "<<j<<endl;
int hi=0,hj=0;
int dp[cnt+1];
for(int k=cnt;k>=1;k--) {
if(a[p[k]]==i) {
dp[k]=hj;
hi++;
}
else {
dp[k]=hi;
hj++;
}
}
//for(int k=1;k<=cnt;k++)cout<<dp[k]<<" ";cout<<endl;
hi=hj=0;
for(int k=cnt;k>=1;k--)
{
if (a[p[k]] == i){
hi = (hi + dp[k]) % mod;
dp[k] = hj;
}else{
hj = (hj + dp[k]) % mod;
dp[k] = hi;
}
}
//for(int k=1;k<=cnt;k++)cout<<dp[k]<<" ";cout<<endl;
hi=hj=0;
for(int k=cnt;k>=1;k--)
{
if (a[p[k]] == i){
hi = (hi + dp[k]) % mod;
dp[k] = hj;
}else{
hj = (hj + dp[k]) % mod;
dp[k] = hi;
}
}
//for(int k=1;k<=cnt;k++)cout<<dp[k]<<" ";cout<<endl;
hi=hj=0;
for(int k=1;k<=cnt;k++) {
if(p[k]>1)ans=(ans+dp[k]*((pre[p[k]-1]-hi*(p[k]-1-hi)-hj*(p[k]-1-hj)+hi*hj)%mod+mod)%mod)%mod;
if(a[p[k]]==i)hi++;
else hj++;
}
}
}
cout<<ans;
}
signed main()
{
//freopen("C:\\Users\\win11\\Desktop\\test.txt", "r", stdin);
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int T = 1;
//cin >> T;
while (T--)solve();
}
/*
// cout << ts[i] << " " << ts[j] << "\n";
// for (int k = 0;k < top;k ++) cout << p[k] << " ";
// cout << "\n";
int dp[top] = {};
int cnti = 0,cntj = 0;
for (int k = top - 1;k >= 0;k --){
if (s[p[k]] == ts[i]){
dp[k] = cntj;
cnti ++;
}else{
dp[k] = cnti;
cntj ++;
}
}
cnti = 0,cntj = 0;
for (int k = top - 1;k >= 0;k --){
if (s[p[k]] == ts[i]){
cnti = (cnti + dp[k]) % mod;
dp[k] = cntj;
}else{
cntj = (cntj + dp[k]) % mod;
dp[k] = cnti;
}
}
cnti = 0,cntj = 0;
for (int k = top - 1;k >= 0;k --){
if (s[p[k]] == ts[i]){
cnti = (cnti + dp[k]) % mod;
dp[k] = cntj;
}else{
cntj = (cntj + dp[k]) % mod;
dp[k] = cnti;
}
}
cnti = 0,cntj = 0;
for (int k = 0;k < top;k ++){
if (p[k] > 1) ans = (ans + dp[k] * ((pre[p[k] - 1] - cnti * (p[k] - cnti) - cntj * (p[k] - cntj) + cnti * cntj) % mod)) % mod;
if (s[p[k]] == ts[i]) cnti ++;
else cntj ++;
}
// cout << ts[i] << " " << ts[j] << " " << ans << "\n";
}
ans = (ans % mod + mod) % mod;
cout << ans << "\n";
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 30188kb
input:
wohaha
output:
1
result:
ok 1 number(s): "1"
Test #2:
score: 0
Accepted
time: 6ms
memory: 30184kb
input:
momomo
output:
0
result:
ok 1 number(s): "0"
Test #3:
score: 0
Accepted
time: 0ms
memory: 28204kb
input:
gshfd1jkhaRaadfglkjerVcvuy0gf
output:
73
result:
ok 1 number(s): "73"
Test #4:
score: 0
Accepted
time: 0ms
memory: 30408kb
input:
retiredMiFaFa0v0
output:
33
result:
ok 1 number(s): "33"
Test #5:
score: 0
Accepted
time: 133ms
memory: 59076kb
input:
bcdccccacccabdbdaddcabddbaccaaaaaabaccbbbcbbddabcbccabacdacbcbabccbcbddcdcbcaaadddddccdbabaabcbbcaaadadacdaadbdccbddddabcbaaddbcadadcbcbaaccacabdababaabdccadaddacdcacdaabbadadaddbbcccbcddaccaadbbcaaccccdcacbdbdddbaccaacbcaccaaabccdadddbaabdbcaaccacdcdcbcdddacbcacdbbbdccdddccccabdbacddacbaacbbcaccdcd...
output:
587599316
result:
ok 1 number(s): "587599316"
Test #6:
score: 0
Accepted
time: 147ms
memory: 57696kb
input:
cedcedaecbbcaceddaacaebeecdaceecdeeedaeebddbcabddeeeeaeeebcbcbabdaeeabddbcebecebaddadacedbacdabcedcecbecedacaedbdaaeaeedcbbcddbbbbdecbeedeadcbdacbeadcadaeeccbdeabedbabbbecbabaaeacdbcbbdedbaebaeadcdcacceeeccedcdcecdbcadcdecbdccadbdbdabbeacbaaacecbabdcecebecaebedcebcccacbcbcdcccdaaaaeacaabeedcbbbaeeea...
output:
604741630
result:
ok 1 number(s): "604741630"
Test #7:
score: 0
Accepted
time: 179ms
memory: 57500kb
input:
dcbbbdcafbfbcdbddfdebcebbfbedfafeadcceeafbdabbbfcefadaedbecbcfaeccdfddbfbeebceadcdeaaefcbecbaececdeddaeefdeaaeaecbdbececdadcacbbefdbbffddeefcecabbecafbbeaaeebedbeabbbaeabedaecffebfcbcfabedebcbadbbfbbebdfdaefcedbdeaacbebcdcbfbfdcabbcadddbdaeabbcdcdfbdfdbcaaaafbfdfabdcdeebcfebecdeacaddeebfecfccadcfdea...
output:
137937394
result:
ok 1 number(s): "137937394"
Test #8:
score: 0
Accepted
time: 207ms
memory: 56772kb
input:
bdfcdcegecbacccddgfdaddgaggefagabgggafgbaeaecgeacacgccadbfdebbdgbaffffgaegabeebacedabecgdfcbbfceeaecaaceebabddbfgefdabgbdbgggdgfegaadccdafgggeafdeecccaafgedfcbefdccafaaaafdcfaeagfeddggcfeeaacgaabadeegebfageeaaceaggddddfcggggdbeefeacdbafggffcdbcaacbaagbcceageaacedceeebacfebgceggffefgabgeaebacdbadcaeg...
output:
830637896
result:
ok 1 number(s): "830637896"
Test #9:
score: 0
Accepted
time: 239ms
memory: 57232kb
input:
bdceebdaahbcgefdbahfcaaaffhfcffgfbaefgehbefdgcgfcafbfdehdeccdbaacdffbhdhdfhdaeehfebgccghchdggcccdbafheaaadhefcbbdeddbfhaehddegcefebghgdahegfefeecbdacffaadbaehahcdbhcdfbacdgfefgeccfgbcbhdfggeecbggbhffceegaahfbahgdebfchhhddfhfcfcdfeddbcabggdfgacaeghechabbdaafbeehgaebfadfchahgdhgggfhehhcehedafhcfcgeegg...
output:
165134706
result:
ok 1 number(s): "165134706"
Test #10:
score: 0
Accepted
time: 260ms
memory: 57724kb
input:
gfgdeabdacecfgadbgbadgbhgafhfhdiageeefghgbhbfhhfaaideehaieaddhcabgdhidbdefeagdfchhccdabchhahgfddchdiegbhfdddefddbcaabhhhgghaafacbbbbaeagacbbdabdidibhgbihdahdeghaheedfechbhfbcabidafeccbcbfdcechdfddffbeagcegagfegdafeaabcafgbcfechhiaiechdhhfdcbceefbccdcadeachcffhaebhbiadgeeggfaeefiaecahdgfgaehcagaaffbc...
output:
729999334
result:
ok 1 number(s): "729999334"
Test #11:
score: 0
Accepted
time: 290ms
memory: 56820kb
input:
hcajfffideibggdfbdjjfbifgdcjibhdedgdibdgfjabaeijabebibcjfaddbiehadgggeadcaedieccdcgigccajjeicgbeijbahjjjghicaigiejgihiabeeggbfjdididdbggfcbhjajbjjgdabihijjddfhdhchggeegiecidjibdcccghfhcffcfehihdedgecbdfjjjiecedfhfjiefhjefbgbieeahcccfggcihbdbgjbdfhhbfghjeaijfagcgchaabijcdedjadfhgbgeefiijhhhcgfjeaadbe...
output:
342396794
result:
ok 1 number(s): "342396794"
Test #12:
score: 0
Accepted
time: 818ms
memory: 56660kb
input:
qsjdnlenipkknuvegwcozcrunnssjmuhdzvzocimsoqzdxsodpsfxhphbwgimyfzzuxowavmsncjjvxdksrambjzbuzkyqdbplbjxrdsacpgbiuzsalkytskdgsxcsblvzyvcgnieysbmeoyfaroxmuetwcvdkhyvlkwqdewldziradjmnkusdsrnybvhylzqroiblkloioqrtybukgmwwxqyjevkijesdddyjagspqqfdmkrhcnjaxcksolmetbutvcigrfhaghmjlzloqkxjooqutmejzhvpmmxzoupjoy...
output:
905453170
result:
ok 1 number(s): "905453170"
Test #13:
score: 0
Accepted
time: 823ms
memory: 55964kb
input:
antlkibnsqqmzaclyvinisylidtvoabqcndzhltrbohfqdfmdzzlyphhqhdbgdgcciyofikhxrqddkcenwhedsjbdwfqcdtrlmdpgpsbxebtwlucklnjqcbjeponmmxfbiuqwhtddfzfephrayohdqfkmzjtjqcywfkcvbtueapgzrlxoecguifcryoygybkkzjkpbmyscnfblbkcolqqeoffahxhbaupbzeazkjjwekeithdymqflpddwpwmpfsvlxwrwkpoetxuborumpzciuytnhgqqzfxbgrqjycqhkd...
output:
82912821
result:
ok 1 number(s): "82912821"
Test #14:
score: 0
Accepted
time: 823ms
memory: 56144kb
input:
khpwaiqnxudrpjjonholcibhhtuokklklxqlxtjzgtqekubgzwhznxzlbowxrseobjzswqvtcvlttnvyxaueqyferdhfbumuzobnmnmoxkkgnxhmykxezptnczshsotuqyqqfmwyuusowieyvskaagzcschzxasckzfezkznakkaeekgyumiabsjhkefbhyrrurqzjalbbecpiiyheqcxifnuwplabncdkweyuqbxhkecujztklbuegdseqzmevordemwmhysmtngpvfdsgskghujbnhkflycnwhbdiorbcw...
output:
659276694
result:
ok 1 number(s): "659276694"
Test #15:
score: 0
Accepted
time: 1925ms
memory: 55372kb
input:
yBsLfzzQCCwjLbfElpCOuMIyMwgSzrQLBnGYJWXFtobNLEGEYDOZUYKyviwbLelicegOrmebrrJkDDsyBDQiFxfHRecxeBUXZikRUctjMLaduPhhbMbgiQjRSrPkZuPoCTcmIrOwxhHTApmNTOwbSrSIKtxlSsVLOuLsfMDqpUHmVTyKzBdUVcJNJdLSDfTLFqVLCJEhkEOadDRRSRRNHefbsKopXMjAgTvXAAnByekMBgzgkbIwMKMeikEKfZzyqVoJVQevMNqXkfROFGjNBqZeDPDTVcTWnxckFdcOsMnj...
output:
916227453
result:
ok 1 number(s): "916227453"
Test #16:
score: 0
Accepted
time: 1930ms
memory: 55208kb
input:
mOGlQDSIpgfWtkiprbIfCGqllMlDEGeykbTgDFMsGSwTYsFcyWvFNkCgGTTXXTIUXrlSiYPWarEebKtOIvHmoljJaZehmSNVNJmqdaiWrRRQOTdNXSHNzYoQTxlaFoHEECYMQSNUnSOcShFbOMTCXdZWYbsNoQmpTouQkNwRlSTFdOBcxnrSXhayNLbScOQsvBZjQWfQSzFuVSyaAVwrTnwQDGvRYqXqyQsUYUPtMTrgVTPzsKhDfveExWfrRhqmqSvvwGbFuNdRSbUCwEiCjpEXPljvhJBMGJSwZBMWYpjc...
output:
205677196
result:
ok 1 number(s): "205677196"
Test #17:
score: 0
Accepted
time: 2368ms
memory: 52700kb
input:
fcD8e11SNuQ6pCULajtOr703RJpyQUDlmMcuP9L3rqRUi3NwKwxy7fnHb3d1RZdtnfFYvZEHJiQ1Woo6ThBnLxdtlBoLIMDvhZrXQTCHnAvnsNtaOfeDBzUZs2QcZstg7qEKo2WEBXAYa1FLLGMeoWfWhCDLE1eIZcepHViqkBXI5xoaUcf6RJApTzbYQnX1nIqkiGQjXUNlATaPByxRHo2ylfaqogW4c61wQVriSUhHerRQD9A3sbivWiJcwCbHpmpwBbmGkhrLYmV7xpwlwTUxgkRWCJ7DQFisYSxRv7QD...
output:
133494571
result:
ok 1 number(s): "133494571"
Test #18:
score: 0
Accepted
time: 2361ms
memory: 52968kb
input:
x4lsq2ZiboEadrneLYd1D3470OktjwPGpjdAtY2KaU2flHECAX68slVa68glymIhK54oblx8QPPRYp5o5k9We7vuCWYk35QHpw3JjkRalGZMN3tPK7MkXYlhrvAS725L7GGQcb4i6wL9Ew2KDxR1mcBAYSJTg7waIChN8q8My9Ifts43gdQGBxPY3PUGb2Motnyi7EMcdVsYbrxYa8RzSi55y84D7M7yWlnmkWnugPzhxgw0f5zCk0F7q4f5yz3jBnEkiInHGZM1a2aUavdOwBtz40XtqMt7eTSIB6hPfD2z...
output:
315491414
result:
ok 1 number(s): "315491414"