QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#558846#7416. GrammarlyWarrnaCuteAC ✓53ms90916kbC++143.1kb2024-09-11 18:51:102024-09-11 18:51:11

Judging History

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

  • [2024-09-11 18:51:11]
  • 评测
  • 测评结果:AC
  • 用时:53ms
  • 内存:90916kb
  • [2024-09-11 18:51:10]
  • 提交

answer

#include<bits/stdc++.h>
#define int long long
using namespace std;
string S;
const int P=998244353;
int fac[1000005],invfac[1000005];
int prefac[1000005];
int power(int x,int y=P-2){
    if(y==0)return 1;
    int tmp=power(x,y>>1);
    if(y&1)return tmp*tmp%P*x%P;
    return tmp*tmp%P;
}
int C(int n,int m){
    return fac[n]*invfac[m]%P*invfac[n-m]%P;
}
int neta[26][300005];
int nxt[300005];
signed main(){
    cin>>S;
    int n=S.size();
    S='?'+S;
    bool flg=false;
    for(int i=2;i<=n;i++){
        if(S[i]!=S[i-1])flg=true;
    }
    if(!flg){
        printf("%lld\n",n);
        return 0;
    }
    fac[0]=1;
    invfac[0]=1;
    for(int i=1;i<=1000000;i++){
        fac[i]=fac[i-1]*i%P;
    }
    prefac[0]=1;
    for(int i=1;i<=1000000;i++){
        prefac[i]=(prefac[i-1]+fac[i])%P;
    }
    invfac[1000000]=power(fac[1000000]);
    for(int i=999999;i>=0;i--){
        invfac[i]=invfac[i+1]*(i+1)%P;
    }
    nxt[n]=n+1;
    for(int i=n-1;i>=1;i--){
        if(S[i]==S[i+1])nxt[i]=nxt[i+1];
        else nxt[i]=i+1;
    }
    int ans=0;
    for(int lt=1;lt<=n;lt++){
        bool tag=false;
        int m=n-nxt[lt];
        ans=(ans+C(lt-1+m+1,lt))%P;
        // for(int j=0;j<=m;j++){
        //     ans=(ans+C(lt-1+j,j))%P;
        // }
    }
    //////////////////////////////
    for(int lt=1;lt<=n;lt++){
        if(lt>1)(neta[S[lt]-'a'][1]+=C((n-1)-1,(lt-1)-1))%=P;
        for(int rt=lt+1;rt<=n+1;rt++){
            if(S[rt]!=S[rt-1]){
                lt=rt-1;
                break;
            }
            //[lt,rt],考虑留着lt-1不删,然后最后把他删了,如果lt=1就不行。
            if(lt>1)(neta[S[lt]-'a'][rt-lt+1]+=C((lt-1+n-rt)-1,(lt-1)-1))%=P;
        }
    }
    for(int rt=n;rt>=1;rt--){
        if(rt<n)(neta[S[rt]-'a'][1]+=C((n-1)-1,(n-rt)-1))%=P;
        for(int lt=rt-1;lt>=0;lt--){
            if(S[lt]!=S[lt+1]){
                rt=lt+1;
                break;
            }
            if(rt<n){
                (neta[S[lt]-'a'][rt-lt+1]+=C((lt-1+n-rt)-1,(n-rt)-1))%=P;
            }
        }
    }
    for(int i=0;i<26;i++){
        for(int j=n;j>=1;j--){
            neta[i][j]+=neta[i][j+1];
            if(neta[i][j]>=P)neta[i][j]-=P;
            ans+=neta[i][j];
            if(ans>=P)ans-=P;
        }
    }
    printf("%lld\n",ans);
    return 0;
}
/*
1. 除非整个子串都相等,否则删左和删右必然本质不同。
2. 如果一个子串,他不是全都是同一个字符,那么他的方案就是一个组合数,这个东西容易计算。
3. 如果一个子串,他是同一个字符,他肯定是包含他的最小的来的,无论顺序他们都是一样的。

枚举字符集,然后枚举这种东西的长度,再枚举他的出现位置(到这里的时间复杂度都是O(n)),然后考虑怎么办嘞,不考虑从比他更大的纯串过来,考虑从旁边消过来,那么方案数也是一个组合数。

最后还要叠加一个点从他上面的消下来的方案数。
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
*/

这程序好像有点Bug,我给组数据试试?

详细

Test #1:

score: 100
Accepted
time: 12ms
memory: 28896kb

input:

abba

output:

13

result:

ok 1 number(s): "13"

Test #2:

score: 0
Accepted
time: 12ms
memory: 28940kb

input:

benbeipo

output:

255

result:

ok 1 number(s): "255"

Test #3:

score: 0
Accepted
time: 8ms
memory: 28160kb

input:

iqiiiiiiqq

output:

300

result:

ok 1 number(s): "300"

Test #4:

score: 0
Accepted
time: 0ms
memory: 4072kb

input:

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa

output:

35

result:

ok 1 number(s): "35"

Test #5:

score: 0
Accepted
time: 0ms
memory: 3808kb

input:

u

output:

1

result:

ok 1 number(s): "1"

Test #6:

score: 0
Accepted
time: 0ms
memory: 3964kb

input:

yy

output:

2

result:

ok 1 number(s): "2"

Test #7:

score: 0
Accepted
time: 12ms
memory: 27708kb

input:

bg

output:

3

result:

ok 1 number(s): "3"

Test #8:

score: 0
Accepted
time: 0ms
memory: 3996kb

input:

qqq

output:

3

result:

ok 1 number(s): "3"

Test #9:

score: 0
Accepted
time: 12ms
memory: 27740kb

input:

yyh

output:

6

result:

ok 1 number(s): "6"

Test #10:

score: 0
Accepted
time: 0ms
memory: 3804kb

input:

cccc

output:

4

result:

ok 1 number(s): "4"

Test #11:

score: 0
Accepted
time: 12ms
memory: 29336kb

input:

kknn

output:

13

result:

ok 1 number(s): "13"

Test #12:

score: 0
Accepted
time: 0ms
memory: 3712kb

input:

ttttt

output:

5

result:

ok 1 number(s): "5"

Test #13:

score: 0
Accepted
time: 12ms
memory: 29240kb

input:

aaaba

output:

25

result:

ok 1 number(s): "25"

Test #14:

score: 0
Accepted
time: 12ms
memory: 27492kb

input:

kktkktktkktttktkttktttkttkttkt

output:

974185013

result:

ok 1 number(s): "974185013"

Test #15:

score: 0
Accepted
time: 12ms
memory: 27848kb

input:

dddydydyddyyyddddydydddydyyyyyydyyyyyyddyydyyddddyyddyydyyyddydyyyyydyddyyydyydydyddydyyddddyyyyydyyyyyyydyddddyydddydydyydddyyyyyyydyydddyydyddydyydddddyyyyyddddyyddyydyddydddyyddyydyyddyyydddyddyyydddyyddydddyyyyydyddydydyydydddyydddyddyydydyddddydyyydyddydddyyddddyydyyydddyddyyydyddydddyyyyyyydyy

output:

267479314

result:

ok 1 number(s): "267479314"

Test #16:

score: 0
Accepted
time: 8ms
memory: 28044kb

input:

ihiiiihihihhhhhihhiiihhihhihihhihihihhiihhhiihiiiiiiihhihiihhhihihihhiiiihhiiiihiihiihihhihhhiihhiiihhhhiiiiihihihhiihiihhhihhiiihhihhiihhiihiiihhiiiihihhihihiihhhiihiihihiihhhhihhhhhhiihhiihihhihhhhhihhiihhiihiiihihhiiiiiihhhiiiiiihhihihiihiiihihhihiiiihhhhhihihhihiihhihhihhiiihiiiiihiiiihhihiiihih...

output:

490411472

result:

ok 1 number(s): "490411472"

Test #17:

score: 0
Accepted
time: 21ms
memory: 33792kb

input:

veeeevvevvvvvvvvvevveveeeveeeeveeeeveevveveevvvvveeeeevvvveeeevvevvvevevveeeevvevvvvvveeeveevvevveeeeeeevevevvevvevevveevvvvveveeeveevevvvvevevveeevvvvvveveevvvveeevvvveevvvveevvvveevvevevveeeeeeveeveveeveeveevevevvvevvevvvvvvevvveevveevvveeevevveeeveeeeeveveeevevveevevevvveeeveevevvevvvveevveeevvev...

output:

395835613

result:

ok 1 number(s): "395835613"

Test #18:

score: 0
Accepted
time: 48ms
memory: 90648kb

input:

eeeeeeeekkkkekkeekkkkeeeeeeeeekeeekkkekkkkekekeeekeekeekekekeekekkkekekeeeekkkkkeekkekeekekkeeeekekeekeekkkeekkkkkekekeekkkeekekekekeeeeeeekkekekeekkeeekekkeekeeekeekkekekekkkkeeekekkeeeeekkkeeeeeeekeeekkkkkkkeeeeeekeeeeeeekeekekkkkeekkkeeeeeeekekekekkkeekeeekkkkkeekkkeeeeekkkeekkeekeeekkeeeekekeekk...

output:

854650474

result:

ok 1 number(s): "854650474"

Test #19:

score: 0
Accepted
time: 16ms
memory: 28404kb

input:

bbibibuibiubbiuubbbibbuibuiuib

output:

931071212

result:

ok 1 number(s): "931071212"

Test #20:

score: 0
Accepted
time: 12ms
memory: 28320kb

input:

ggxgyxxgyyyyyggxxggxyxygxyxggyygggggggxggxyxggxgxxgxyygygxxyxxgxggxxgxggyxxxgggygxyxgggyyyxxxxxgyxggxygygyygyxgyggggxxygggxgyyyyyxxyyxgxyxxyygxxxxxgyyygygxygxyxxyxggyxyxygygxygxgxgxggyggyggxyxyyxygxyxxygxyxyygxyygxxyxxygyyggyyggygxxxgggxgxyyggxygyxgxxxxgxggygyygxggygygxyyyxyxxxggxgxxygxgxxygyggygggx

output:

649661487

result:

ok 1 number(s): "649661487"

Test #21:

score: 0
Accepted
time: 6ms
memory: 29424kb

input:

otohhhotohhhotohthotooththtothohthtttthhhoohotooohhohhohhooohhtotthtoototohhoohoohhotottoooohhothtohohththtthttotoohtothttothohoohtoooththoooohhhoooohtohotthttthothoohohhotothothhtthohhooooohotooothhhttthooothttthhotohttohttthtthttotthhthhtohtotthhohhthohooohotottothohttohhtohttoootohhhtoohttoootthh...

output:

965561176

result:

ok 1 number(s): "965561176"

Test #22:

score: 0
Accepted
time: 11ms
memory: 34948kb

input:

nneeenennezzezeeeznnzznenneenzzeezznzzeezneezzznnenzneennnnznnnneeznenezzznnezezeeznnezenznzneznzzzenenzznnzeezenenzneeznnenenezzenezzenznzzeeeezezenzenzennzneezzezzennezzznnzenneeznnneezeeenezeezeeezneeeznneeeenneznznezeennzzeenzezznennznznnennnzzznnznneneeennneeeeznezzznnneznzenennzzeznzezzezzennn...

output:

963316318

result:

ok 1 number(s): "963316318"

Test #23:

score: 0
Accepted
time: 36ms
memory: 90640kb

input:

fuuulfuulllffllfuulfflffufluufffuflufuffllluullffffluuflulfulullfffluuullulfuufullluuflfllffllluululffflluuulluflulufufufflllulllffflfuufulfllfflulfluufllfllluulfullfuflllfuufuulfufffulfuulfuuuuulllfffllflufulflufuflluulfulfuulfuluuululuufllluuuulullufffluluflfffuuuluuuuuluffuuffffffuuuuuuulflufufll...

output:

469546709

result:

ok 1 number(s): "469546709"

Test #24:

score: 0
Accepted
time: 4ms
memory: 3900kb

input:

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

300000

result:

ok 1 number(s): "300000"

Test #25:

score: 0
Accepted
time: 27ms
memory: 90644kb

input:

kekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekeke...

output:

526952119

result:

ok 1 number(s): "526952119"

Test #26:

score: 0
Accepted
time: 53ms
memory: 90908kb

input:

keekekkeekkekeekekkekeekkeekekkeekkekeekkeekekkekeekekkeekkekeekekkekeekkeekekkekeekekkeekkekeekkeekekkeekkekeekekkekeekkeekekkeekkekeekkeekekkekeekekkeekkekeekkeekekkeekkekeekekkekeekkeekekkekeekekkeekkekeekekkekeekkeekekkeekkekeekkeekekkekeekekkeekkekeekekkekeekkeekekkekeekekkeekkekeekkeekekkeekke...

output:

232335975

result:

ok 1 number(s): "232335975"

Test #27:

score: 0
Accepted
time: 27ms
memory: 90504kb

input:

zkanrscwyqzkanrscwyqzkanrscwyqzkanrscwyqzkanrscwyqzkanrscwyqzkanrscwyqzkanrscwyqzkanrscwyqzkanrscwyqzkanrscwyqzkanrscwyqzkanrscwyqzkanrscwyqzkanrscwyqzkanrscwyqzkanrscwyqzkanrscwyqzkanrscwyqzkanrscwyqzkanrscwyqzkanrscwyqzkanrscwyqzkanrscwyqzkanrscwyqzkanrscwyqzkanrscwyqzkanrscwyqzkanrscwyqzkanrscwyq...

output:

526952119

result:

ok 1 number(s): "526952119"

Test #28:

score: 0
Accepted
time: 47ms
memory: 90548kb

input:

zkkakaankaanannrkaanannrannrnrrskaanannrannrnrrsannrnrrsnrrsrssckaanannrannrnrrsannrnrrsnrrsrsscannrnrrsnrrsrsscnrrsrsscrsscsccwkaanannrannrnrrsannrnrrsnrrsrsscannrnrrsnrrsrsscnrrsrsscrsscsccwannrnrrsnrrsrsscnrrsrsscrsscsccwnrrsrsscrsscsccwrsscsccwsccwcwwykaanannrannrnrrsannrnrrsnrrsrsscannrnrrsnrrs...

output:

292840925

result:

ok 1 number(s): "292840925"

Test #29:

score: 0
Accepted
time: 35ms
memory: 90612kb

input:

yiajzosxvkbufdtqcemhpgwnlryiajzosxvkbufdtqcemhpgwnlryiajzosxvkbufdtqcemhpgwnlryiajzosxvkbufdtqcemhpgwnlryiajzosxvkbufdtqcemhpgwnlryiajzosxvkbufdtqcemhpgwnlryiajzosxvkbufdtqcemhpgwnlryiajzosxvkbufdtqcemhpgwnlryiajzosxvkbufdtqcemhpgwnlryiajzosxvkbufdtqcemhpgwnlryiajzosxvkbufdtqcemhpgwnlryiajzosxvkbufd...

output:

526952119

result:

ok 1 number(s): "526952119"

Test #30:

score: 0
Accepted
time: 24ms
memory: 90576kb

input:

yiiaiaajiaajajjziaajajjzajjzjzzoiaajajjzajjzjzzoajjzjzzojzzozoosiaajajjzajjzjzzoajjzjzzojzzozoosajjzjzzojzzozoosjzzozooszoosossxiaajajjzajjzjzzoajjzjzzojzzozoosajjzjzzojzzozoosjzzozooszoosossxajjzjzzojzzozoosjzzozooszoosossxjzzozooszoosossxzoosossxossxsxxviaajajjzajjzjzzoajjzjzzojzzozoosajjzjzzojzzo...

output:

538020582

result:

ok 1 number(s): "538020582"

Test #31:

score: 0
Accepted
time: 35ms
memory: 90632kb

input:

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

436599269

result:

ok 1 number(s): "436599269"

Test #32:

score: 0
Accepted
time: 49ms
memory: 90548kb

input:

yyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyy...

output:

452097214

result:

ok 1 number(s): "452097214"

Test #33:

score: 0
Accepted
time: 43ms
memory: 90628kb

input:

kkkkkkkkkkkkkkkkkkkkkksssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssscccccccccccccccccccccccccccccccccccccccccccccccccccccc...

output:

51148515

result:

ok 1 number(s): "51148515"

Test #34:

score: 0
Accepted
time: 45ms
memory: 90804kb

input:

rrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrryyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggccccccccccccccccccccccccccccccccccccccccc...

output:

398270601

result:

ok 1 number(s): "398270601"

Test #35:

score: 0
Accepted
time: 27ms
memory: 90612kb

input:

eehhhhhhhhhhhhhhhhhhhmmmwwwwwrrrrrrrrrrzzzzzzzzzzzzzzzzhhhhppppppppppppppppppppppppkkkkklllllggggggquuuukrrrrrrrzzzzzzzzzzzppppjjjjjjjjjjjjjjjjjjjgggggggggggzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzkkkkkkkklldddddduuuuutttttttttttttxxxxxxxxxxxxdddddddddddddddmmmmmmddddddddddddbbbbbbccccccmoooooooooo...

output:

685442319

result:

ok 1 number(s): "685442319"

Test #36:

score: 0
Accepted
time: 32ms
memory: 90556kb

input:

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

360917686

result:

ok 1 number(s): "360917686"

Test #37:

score: 0
Accepted
time: 45ms
memory: 90576kb

input:

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

450457957

result:

ok 1 number(s): "450457957"

Test #38:

score: 0
Accepted
time: 34ms
memory: 90568kb

input:

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

679473094

result:

ok 1 number(s): "679473094"

Test #39:

score: 0
Accepted
time: 31ms
memory: 90640kb

input:

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

215673856

result:

ok 1 number(s): "215673856"

Test #40:

score: 0
Accepted
time: 39ms
memory: 90840kb

input:

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

940702393

result:

ok 1 number(s): "940702393"

Test #41:

score: 0
Accepted
time: 49ms
memory: 90448kb

input:

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

389598315

result:

ok 1 number(s): "389598315"

Test #42:

score: 0
Accepted
time: 39ms
memory: 90572kb

input:

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

617812509

result:

ok 1 number(s): "617812509"

Test #43:

score: 0
Accepted
time: 28ms
memory: 90552kb

input:

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

689671191

result:

ok 1 number(s): "689671191"

Test #44:

score: 0
Accepted
time: 41ms
memory: 90632kb

input:

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

505827379

result:

ok 1 number(s): "505827379"

Test #45:

score: 0
Accepted
time: 39ms
memory: 90552kb

input:

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

290367667

result:

ok 1 number(s): "290367667"

Test #46:

score: 0
Accepted
time: 41ms
memory: 90508kb

input:

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

631912358

result:

ok 1 number(s): "631912358"

Test #47:

score: 0
Accepted
time: 46ms
memory: 90636kb

input:

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

433834157

result:

ok 1 number(s): "433834157"

Test #48:

score: 0
Accepted
time: 40ms
memory: 90908kb

input:

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

729374198

result:

ok 1 number(s): "729374198"

Test #49:

score: 0
Accepted
time: 45ms
memory: 90548kb

input:

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

11646013

result:

ok 1 number(s): "11646013"

Test #50:

score: 0
Accepted
time: 31ms
memory: 90780kb

input:

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

351477104

result:

ok 1 number(s): "351477104"

Test #51:

score: 0
Accepted
time: 24ms
memory: 90644kb

input:

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

957526281

result:

ok 1 number(s): "957526281"

Test #52:

score: 0
Accepted
time: 45ms
memory: 90576kb

input:

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

529641898

result:

ok 1 number(s): "529641898"

Test #53:

score: 0
Accepted
time: 47ms
memory: 90548kb

input:

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

210262893

result:

ok 1 number(s): "210262893"

Test #54:

score: 0
Accepted
time: 37ms
memory: 90632kb

input:

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

911032433

result:

ok 1 number(s): "911032433"

Test #55:

score: 0
Accepted
time: 43ms
memory: 90608kb

input:

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

937163682

result:

ok 1 number(s): "937163682"

Test #56:

score: 0
Accepted
time: 45ms
memory: 90552kb

input:

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

334206357

result:

ok 1 number(s): "334206357"

Test #57:

score: 0
Accepted
time: 35ms
memory: 90916kb

input:

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

827627696

result:

ok 1 number(s): "827627696"

Test #58:

score: 0
Accepted
time: 41ms
memory: 90580kb

input:

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

686365858

result:

ok 1 number(s): "686365858"

Test #59:

score: 0
Accepted
time: 27ms
memory: 90572kb

input:

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

974448194

result:

ok 1 number(s): "974448194"

Test #60:

score: 0
Accepted
time: 46ms
memory: 90804kb

input:

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

670612527

result:

ok 1 number(s): "670612527"