QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#558646 | #7416. Grammarly | hmya# | TL | 1508ms | 34784kb | C++14 | 3.0kb | 2024-09-11 17:16:59 | 2024-09-11 17:17:01 |
Judging History
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
*/
详细
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...