QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #307143 | #5051. Namomo Subsequence | The_Owls | TL | 1780ms | 216320kb | C++23 | 6.9kb | 2024-01-18 01:24:51 | 2024-01-18 01:24:51 |
Judging History
answer
#include<bits/stdc++.h>
//#pragma GCC optimize("Ofast,unroll-loops")
//#pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2,fma,tune=native")
#define FAST ios_base::sync_with_stdio(false); \
cin.tie(0); \
cout.tie(0);
#define ll long long
#define ull unsigned long long
#define el '\n'
#define sp ' '
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define ppb pop_back
using namespace std ;
typedef unsigned char Byte ;
const int mod = 998244353 ;
void solve_this_testcase ()
{
string s ; cin >> s ;
int n = s.size();
unordered_map < char, int > M ;
for ( int i = 0 ; i < 10 ; ++ i ) M[char(i+48)] = i ;
for ( int i = 0 ; i < 26 ; ++ i ) M[char(i+65)] = i + 10 ;
for ( int i = 0 ; i < 26 ; ++ i ) M[char(i+97)] = i + 10 + 26 ;
int L [n] ;
for ( int i = 0 ; i < n ; ++ i ) L[i] = M[s[i]] ;
array < vector < int > , 62 > O ;
for ( int i = 0 ; i < n ; ++ i ) O[L[i]].pb(i) ;
array < array < vector < pair < int , int > > , 62 > , 62 > D ;
for ( int i = 0 ; i < 62 ; ++ i )
{
for ( int j = 0 ; j < 62 ; ++ j )
{
if ( O[i].size() == 0 or O[j].size() == 0 or i == j ) continue ;
int a = 0;
int b = 0;
int szj = O[j].size() ;
while ( a < O[i].size() and b < O[j].size() )
{
while ( b < O[j].size() and O[j][b] < O[i][a] ) b += 1;
D[i][j].pb(mp(O[i][a],szj-b));
a += 1;
}
for ( int k = D[i][j].size() - 2 ; k >= 0 ; --k )
{
D[i][j][k].se += D[i][j][k+1].se ;
if ( D[i][j][k].se >= mod ) D[i][j][k].se -= mod ;
}
}
}
for ( int i = 0 ; i < 62 ; ++ i )
{
for ( int j = 0 ; j < 62 ; ++ j )
{
if ( O[i].size() == 0 or D[j][i].size() == 0 or i == j )
{
D[j][i].clear();
continue ;
}
vector < pair < int , int > > V ;
int a = 0;
int b = 0;
while ( a < O[i].size() and b < D[j][i].size() )
{
while ( b < D[j][i].size() and D[j][i][b].fi < O[i][a] ) b += 1;
if ( b != D[j][i].size() ) V.pb(mp(O[i][a],D[j][i][b].se));
a += 1;
}
for ( int k = V.size() - 2 ; k >= 0 ; --k )
{
V[k].se += V[k+1].se ;
if ( V[k].se > mod ) V[k].se -= mod ;
}
D[j][i] = V ;
}
}
for ( int i = 0 ; i < 62 ; ++ i )
{
for ( int j = 0 ; j < 62 ; ++ j )
{
if ( O[i].size() == 0 or D[i][j].size() == 0 or i == j )
{
D[i][j].clear();
continue ;
}
vector < pair < int , int > > V ;
int a = 0;
int b = 0;
while ( a < O[i].size() and b < D[i][j].size() )
{
while ( b < D[i][j].size() and D[i][j][b].fi < O[i][a] ) b += 1;
if ( b != D[i][j].size() ) V.pb(mp(O[i][a],D[i][j][b].se));
a += 1;
}
for ( int k = V.size() - 2 ; k >= 0 ; --k )
{
V[k].se += V[k+1].se ;
if ( V[k].se > mod ) V[k].se -= mod ;
}
D[i][j] = V ;
}
}
int V [n];
for ( int i = 0 ; i < n ; ++i ) V[i] = 0;
for ( int i = 0 ; i < 62 ; ++ i )
{
for ( int j = 0 ; j < 62 ; ++ j )
{
if ( D[i][j].size() == 0 or i == j )
{
continue ;
}
V[0] += D[i][j][0].se ;
V[0] %= mod;
for ( int k = 0 ; k < D[i][j].size() - 1 ; ++k )
{
V[D[i][j][k].fi+1] += D[i][j][k+1].se - D[i][j][k].se ;
if ( V[D[i][j][k].fi+1] < 0 ) V[D[i][j][k].fi+1] += mod ;
else if ( V[D[i][j][k].fi+1] >= mod ) V[D[i][j][k].fi+1] -= mod ;
}
V[D[i][j][D[i][j].size()-1].fi+1] = V[D[i][j][D[i][j].size()-1].fi+1] - D[i][j][D[i][j].size()-1].se + mod ;
if ( V[D[i][j][D[i][j].size()-1].fi+1] < 0 ) V[D[i][j][D[i][j].size()-1].fi+1] += mod ;
else if ( V[D[i][j][D[i][j].size()-1].fi+1] >= mod ) V[D[i][j][D[i][j].size()-1].fi+1] -= mod ;
}
}
for ( int i = 1 ; i < n ; ++i )
{
V[i] += V[i-1] ;
if ( V[i] >= mod ) V[i] -= mod ;
}
int C [62][62] ;
for ( int i = 0 ; i < 62 ; ++ i )
{
for ( int j = 0 ; j < 62 ; ++ j )
{
C[i][j] = 0 ;
}
}
int CC[62] ;
for ( int i = 0 ; i < 62 ; ++ i )
{
CC[i] = 0 ;
}
int ans = 0 ;
int S[62] ;
for ( int i = 0 ; i < 62 ; ++ i ) S[i] = O[i].size() ;
for ( int h = n -1 ; h > -1 ; -- h )
{
int i = L[h] ;
for ( int j = 0 ; j < 62 ; ++ j )
{
if ( i == j ) continue ;
if ( D[i][j].size() != 0 and D[i][j][D[i][j].size()-1].fi >= h )
{
CC[i] += D[i][j][D[i][j].size()-1].se - C[i][j] ;
if ( CC[i] < 0 ) CC[i] += mod ;
else if ( CC[i] >= mod ) CC[i] -= mod ;
CC[j] += D[i][j][D[i][j].size()-1].se - C[i][j] ;
if ( CC[j] < 0 ) CC[j] += mod ;
else if ( CC[j] >= mod ) CC[j] -= mod ;
C[i][j] = D[i][j][D[i][j].size()-1].se ;
D[i][j].ppb() ;
}
}
for ( int j = 0 ; j < 62 ; ++ j )
{
if ( i == j ) continue ;
ll v = V[h] ;
v = v - CC[i] + mod ;
if ( v > mod ) v -= mod ;
v = v - CC[j] + mod ;
if ( v > mod ) v -= mod ;
v += C[i][j] ;
if ( v > mod ) v -= mod ;
v += C[j][i] ;
if ( v > mod ) v -= mod ;
v *= S[j] ;
v %= mod ;
ans += v;
//ans += ( S[j] * ( ( ( V[h] - CC[i] - CC[j] + C[i][j] + C[j][i] ) + mod ) % mod ) ) % mod ;
if ( ans > mod ) ans -= mod ;
}
S[i] -= 1;
}
cout << ans%mod << el ;
}
int main()
{
FAST
ll test = 1 ;
//cin >> test ;
for ( ll testtest = 0 ; testtest < test ; testtest ++ )
{
solve_this_testcase ( ) ;
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3640kb
input:
wohaha
output:
1
result:
ok 1 number(s): "1"
Test #2:
score: 0
Accepted
time: 1ms
memory: 3688kb
input:
momomo
output:
0
result:
ok 1 number(s): "0"
Test #3:
score: 0
Accepted
time: 0ms
memory: 3844kb
input:
gshfd1jkhaRaadfglkjerVcvuy0gf
output:
73
result:
ok 1 number(s): "73"
Test #4:
score: 0
Accepted
time: 1ms
memory: 3828kb
input:
retiredMiFaFa0v0
output:
33
result:
ok 1 number(s): "33"
Test #5:
score: 0
Accepted
time: 417ms
memory: 39480kb
input:
bcdccccacccabdbdaddcabddbaccaaaaaabaccbbbcbbddabcbccabacdacbcbabccbcbddcdcbcaaadddddccdbabaabcbbcaaadadacdaadbdccbddddabcbaaddbcadadcbcbaaccacabdababaabdccadaddacdcacdaabbadadaddbbcccbcddaccaadbbcaaccccdcacbdbdddbaccaacbcaccaaabccdadddbaabdbcaaccacdcdcbcdddacbcacdbbbdccdddccccabdbacddacbaacbbcaccdcd...
output:
587599316
result:
ok 1 number(s): "587599316"
Test #6:
score: 0
Accepted
time: 482ms
memory: 47344kb
input:
cedcedaecbbcaceddaacaebeecdaceecdeeedaeebddbcabddeeeeaeeebcbcbabdaeeabddbcebecebaddadacedbacdabcedcecbecedacaedbdaaeaeedcbbcddbbbbdecbeedeadcbdacbeadcadaeeccbdeabedbabbbecbabaaeacdbcbbdedbaebaeadcdcacceeeccedcdcecdbcadcdecbdccadbdbdabbeacbaaacecbabdcecebecaebedcebcccacbcbcdcccdaaaaeacaabeedcbbbaeeea...
output:
604741630
result:
ok 1 number(s): "604741630"
Test #7:
score: 0
Accepted
time: 533ms
memory: 55140kb
input:
dcbbbdcafbfbcdbddfdebcebbfbedfafeadcceeafbdabbbfcefadaedbecbcfaeccdfddbfbeebceadcdeaaefcbecbaececdeddaeefdeaaeaecbdbececdadcacbbefdbbffddeefcecabbecafbbeaaeebedbeabbbaeabedaecffebfcbcfabedebcbadbbfbbebdfdaefcedbdeaacbebcdcbfbfdcabbcadddbdaeabbcdcdfbdfdbcaaaafbfdfabdcdeebcfebecdeacaddeebfecfccadcfdea...
output:
137937394
result:
ok 1 number(s): "137937394"
Test #8:
score: 0
Accepted
time: 596ms
memory: 63548kb
input:
bdfcdcegecbacccddgfdaddgaggefagabgggafgbaeaecgeacacgccadbfdebbdgbaffffgaegabeebacedabecgdfcbbfceeaecaaceebabddbfgefdabgbdbgggdgfegaadccdafgggeafdeecccaafgedfcbefdccafaaaafdcfaeagfeddggcfeeaacgaabadeegebfageeaaceaggddddfcggggdbeefeacdbafggffcdbcaacbaagbcceageaacedceeebacfebgceggffefgabgeaebacdbadcaeg...
output:
830637896
result:
ok 1 number(s): "830637896"
Test #9:
score: 0
Accepted
time: 634ms
memory: 73164kb
input:
bdceebdaahbcgefdbahfcaaaffhfcffgfbaefgehbefdgcgfcafbfdehdeccdbaacdffbhdhdfhdaeehfebgccghchdggcccdbafheaaadhefcbbdeddbfhaehddegcefebghgdahegfefeecbdacffaadbaehahcdbhcdfbacdgfefgeccfgbcbhdfggeecbggbhffceegaahfbahgdebfchhhddfhfcfcdfeddbcabggdfgacaeghechabbdaafbeehgaebfadfchahgdhgggfhehhcehedafhcfcgeegg...
output:
165134706
result:
ok 1 number(s): "165134706"
Test #10:
score: 0
Accepted
time: 679ms
memory: 80952kb
input:
gfgdeabdacecfgadbgbadgbhgafhfhdiageeefghgbhbfhhfaaideehaieaddhcabgdhidbdefeagdfchhccdabchhahgfddchdiegbhfdddefddbcaabhhhgghaafacbbbbaeagacbbdabdidibhgbihdahdeghaheedfechbhfbcabidafeccbcbfdcechdfddffbeagcegagfegdafeaabcafgbcfechhiaiechdhhfdcbceefbccdcadeachcffhaebhbiadgeeggfaeefiaecahdgfgaehcagaaffbc...
output:
729999334
result:
ok 1 number(s): "729999334"
Test #11:
score: 0
Accepted
time: 748ms
memory: 89504kb
input:
hcajfffideibggdfbdjjfbifgdcjibhdedgdibdgfjabaeijabebibcjfaddbiehadgggeadcaedieccdcgigccajjeicgbeijbahjjjghicaigiejgihiabeeggbfjdididdbggfcbhjajbjjgdabihijjddfhdhchggeegiecidjibdcccghfhcffcfehihdedgecbdfjjjiecedfhfjiefhjefbgbieeahcccfggcihbdbgjbdfhhbfghjeaijfagcgchaabijcdedjadfhgbgeefiijhhhcgfjeaadbe...
output:
342396794
result:
ok 1 number(s): "342396794"
Test #12:
score: 0
Accepted
time: 1780ms
memory: 216320kb
input:
qsjdnlenipkknuvegwcozcrunnssjmuhdzvzocimsoqzdxsodpsfxhphbwgimyfzzuxowavmsncjjvxdksrambjzbuzkyqdbplbjxrdsacpgbiuzsalkytskdgsxcsblvzyvcgnieysbmeoyfaroxmuetwcvdkhyvlkwqdewldziradjmnkusdsrnybvhylzqroiblkloioqrtybukgmwwxqyjevkijesdddyjagspqqfdmkrhcnjaxcksolmetbutvcigrfhaghmjlzloqkxjooqutmejzhvpmmxzoupjoy...
output:
905453170
result:
ok 1 number(s): "905453170"
Test #13:
score: 0
Accepted
time: 1754ms
memory: 216148kb
input:
antlkibnsqqmzaclyvinisylidtvoabqcndzhltrbohfqdfmdzzlyphhqhdbgdgcciyofikhxrqddkcenwhedsjbdwfqcdtrlmdpgpsbxebtwlucklnjqcbjeponmmxfbiuqwhtddfzfephrayohdqfkmzjtjqcywfkcvbtueapgzrlxoecguifcryoygybkkzjkpbmyscnfblbkcolqqeoffahxhbaupbzeazkjjwekeithdymqflpddwpwmpfsvlxwrwkpoetxuborumpzciuytnhgqqzfxbgrqjycqhkd...
output:
82912821
result:
ok 1 number(s): "82912821"
Test #14:
score: 0
Accepted
time: 1741ms
memory: 216188kb
input:
khpwaiqnxudrpjjonholcibhhtuokklklxqlxtjzgtqekubgzwhznxzlbowxrseobjzswqvtcvlttnvyxaueqyferdhfbumuzobnmnmoxkkgnxhmykxezptnczshsotuqyqqfmwyuusowieyvskaagzcschzxasckzfezkznakkaeekgyumiabsjhkefbhyrrurqzjalbbecpiiyheqcxifnuwplabncdkweyuqbxhkecujztklbuegdseqzmevordemwmhysmtngpvfdsgskghujbnhkflycnwhbdiorbcw...
output:
659276694
result:
ok 1 number(s): "659276694"
Test #15:
score: -100
Time Limit Exceeded
input:
yBsLfzzQCCwjLbfElpCOuMIyMwgSzrQLBnGYJWXFtobNLEGEYDOZUYKyviwbLelicegOrmebrrJkDDsyBDQiFxfHRecxeBUXZikRUctjMLaduPhhbMbgiQjRSrPkZuPoCTcmIrOwxhHTApmNTOwbSrSIKtxlSsVLOuLsfMDqpUHmVTyKzBdUVcJNJdLSDfTLFqVLCJEhkEOadDRRSRRNHefbsKopXMjAgTvXAAnByekMBgzgkbIwMKMeikEKfZzyqVoJVQevMNqXkfROFGjNBqZeDPDTVcTWnxckFdcOsMnj...