QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#558646#7416. Grammarlyhmya#TL 1508ms34784kbC++143.0kb2024-09-11 17:16:592024-09-11 17:17:01

Judging History

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

  • [2024-09-11 17:17:01]
  • 评测
  • 测评结果:TL
  • 用时:1508ms
  • 内存:34784kb
  • [2024-09-11 17:16:59]
  • 提交

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];
        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
*/

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

abba

output:

13

result:

ok 1 number(s): "13"

Test #2:

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

input:

benbeipo

output:

255

result:

ok 1 number(s): "255"

Test #3:

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

input:

iqiiiiiiqq

output:

300

result:

ok 1 number(s): "300"

Test #4:

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

input:

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa

output:

35

result:

ok 1 number(s): "35"

Test #5:

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

input:

u

output:

1

result:

ok 1 number(s): "1"

Test #6:

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

input:

yy

output:

2

result:

ok 1 number(s): "2"

Test #7:

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

input:

bg

output:

3

result:

ok 1 number(s): "3"

Test #8:

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

input:

qqq

output:

3

result:

ok 1 number(s): "3"

Test #9:

score: 0
Accepted
time: 13ms
memory: 29196kb

input:

yyh

output:

6

result:

ok 1 number(s): "6"

Test #10:

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

input:

cccc

output:

4

result:

ok 1 number(s): "4"

Test #11:

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

input:

kknn

output:

13

result:

ok 1 number(s): "13"

Test #12:

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

input:

ttttt

output:

5

result:

ok 1 number(s): "5"

Test #13:

score: 0
Accepted
time: 9ms
memory: 28748kb

input:

aaaba

output:

25

result:

ok 1 number(s): "25"

Test #14:

score: 0
Accepted
time: 10ms
memory: 28836kb

input:

kktkktktkktttktkttktttkttkttkt

output:

974185013

result:

ok 1 number(s): "974185013"

Test #15:

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

input:

dddydydyddyyyddddydydddydyyyyyydyyyyyyddyydyyddddyyddyydyyyddydyyyyydyddyyydyydydyddydyyddddyyyyydyyyyyyydyddddyydddydydyydddyyyyyyydyydddyydyddydyydddddyyyyyddddyyddyydyddydddyyddyydyyddyyydddyddyyydddyyddydddyyyyydyddydydyydydddyydddyddyydydyddddydyyydyddydddyyddddyydyyydddyddyyydyddydddyyyyyyydyy

output:

267479314

result:

ok 1 number(s): "267479314"

Test #16:

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

input:

ihiiiihihihhhhhihhiiihhihhihihhihihihhiihhhiihiiiiiiihhihiihhhihihihhiiiihhiiiihiihiihihhihhhiihhiiihhhhiiiiihihihhiihiihhhihhiiihhihhiihhiihiiihhiiiihihhihihiihhhiihiihihiihhhhihhhhhhiihhiihihhihhhhhihhiihhiihiiihihhiiiiiihhhiiiiiihhihihiihiiihihhihiiiihhhhhihihhihiihhihhihhiiihiiiiihiiiihhihiiihih...

output:

490411472

result:

ok 1 number(s): "490411472"

Test #17:

score: 0
Accepted
time: 1508ms
memory: 34784kb

input:

veeeevvevvvvvvvvvevveveeeveeeeveeeeveevveveevvvvveeeeevvvveeeevvevvvevevveeeevvevvvvvveeeveevvevveeeeeeevevevvevvevevveevvvvveveeeveevevvvvevevveeevvvvvveveevvvveeevvvveevvvveevvvveevvevevveeeeeeveeveveeveeveevevevvvevvevvvvvvevvveevveevvveeevevveeeveeeeeveveeevevveevevevvveeeveevevvevvvveevveeevvev...

output:

395835613

result:

ok 1 number(s): "395835613"

Test #18:

score: -100
Time Limit Exceeded

input:

eeeeeeeekkkkekkeekkkkeeeeeeeeekeeekkkekkkkekekeeekeekeekekekeekekkkekekeeeekkkkkeekkekeekekkeeeekekeekeekkkeekkkkkekekeekkkeekekekekeeeeeeekkekekeekkeeekekkeekeeekeekkekekekkkkeeekekkeeeeekkkeeeeeeekeeekkkkkkkeeeeeekeeeeeeekeekekkkkeekkkeeeeeeekekekekkkeekeeekkkkkeekkkeeeeekkkeekkeekeeekkeeeekekeekk...

output:


result: