QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#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

你现在查看的是最新测评结果

[2024-01-18 01:24:51]
评测

测评结果：TL
用时：1780ms
内存：216320kb

查看

[2024-01-18 01:24:51]
提交

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 ( ) ;
    
    }
 
}

源文件, 语言: C++23

详细

Test #1:

score: 100

Accepted

time: 1ms

memory: 3640kb

input:

wohaha

output:

result:

ok 1 number(s): "1"

Test #2:

score: 0

Accepted

time: 1ms

memory: 3688kb

input:

momomo

output:

result:

ok 1 number(s): "0"

Test #3:

score: 0

Accepted

time: 0ms

memory: 3844kb

input:

gshfd1jkhaRaadfglkjerVcvuy0gf

output:

result:

ok 1 number(s): "73"

Test #4:

score: 0

Accepted

time: 1ms

memory: 3828kb

input:

retiredMiFaFa0v0

output:

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...