QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#192242 | #7512. Almost Prefix Concatenation | ucup-team896# | TL | 16ms | 22084kb | C++14 | 1.3kb | 2023-09-30 14:02:50 | 2023-09-30 14:02:50 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define ull unsigned long long
#define ll long long
ull bs=19260817;
const ll N=1e6+37,mod=998244353;
char s[N],t[N];
int n,m,nxt[N];ll ans[N];
ll dp[N],dp2[N],tg[N],tg2[N];
ull hs[N],pw[N],ht[N];
ull gt(int x,int y){
return hs[y]-hs[x-1]*pw[y-x+1];
}ull gt2(int x,int y){
return ht[y]-ht[x-1]*pw[y-x+1];
}signed main(){
ios::sync_with_stdio(0);
cin.tie(0);cin>>(s+1)>>(t+1);
n=strlen(s+1),m=strlen(t+1);
pw[0]=1;
for(int i=1;i<N;i++)
pw[i]=pw[i-1]*bs;
for(int i=1;i<=n;i++)
hs[i]=bs*hs[i-1]+(ull)(s[i]-'a'+1);
for(int i=1;i<=m;i++)
ht[i]=bs*ht[i-1]+(ull)(t[i]-'a'+1);
for(int i=1;i<=n;i++){
int l=i,r=min(n,i+m-1),as=i-1;
while(l<=r){
int mid=(l+r)>>1;
if(gt(i,mid)==ht[mid-i+1]){
as=mid;
l=mid+1;
}else r=mid-1;
}nxt[i]=as;
}for(int i=n+1;i<=n+7;i++)
nxt[i]=i;
for(int i=n;i;i--){
int to=nxt[i]+2,l=to,r=n,as=l-1;
while(l<=r){
int mid=(l+r)>>1;
if(gt(to,mid)==gt2(to-i+1,mid-i+1)){
as=mid;
l=mid+1;
}else r=mid-1;
}nxt[i]=as;
nxt[i]=min(nxt[i],min(n,i+m-1));
}dp[0]=dp2[0]=1;
for(int i=0;i<n;i++){
int l=i+1,r=min(n,nxt[i+1]);
for(int j=l;j<=r;j++){
dp[j]=(dp[j]+dp[i])%mod;
dp2[j]=(dp2[j]+dp2[i]+2*dp[i])%mod;
ans[j]=(ans[j]+dp2[i]+ans[i])%mod;
}
}cout<<ans[n]<<"\n";
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 19756kb
input:
ababaab aba
output:
473
result:
ok 1 number(s): "473"
Test #2:
score: 0
Accepted
time: 0ms
memory: 21864kb
input:
ac ccpc
output:
5
result:
ok 1 number(s): "5"
Test #3:
score: 0
Accepted
time: 2ms
memory: 21864kb
input:
qqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqq...
output:
75038697
result:
ok 1 number(s): "75038697"
Test #4:
score: 0
Accepted
time: 0ms
memory: 21864kb
input:
lvvvllvllvllvllllllllvvvllvlllvvlvlvllvlvvlvvvvlvvllllllvvlvlvvlllvvlvlvllllllvlvvvvvvlllvvvllvlvvvlvvlllvvvvvvlvlllvvvvlvvvvvlvvlvvlllvvllvvllvlvlvlvlvllllvvllvvllvlllvvvllllvvlvvllvvvvlvlvvlvvlllvvvvvvvvlvvlvlllvllvvvvllvvvlvvvvvvlvlllvllllvllllllllvvllllllvlvvlvvvlvllllvllvlvvllllllvlvvvlvlvlvvvl...
output:
538419149
result:
ok 1 number(s): "538419149"
Test #5:
score: 0
Accepted
time: 0ms
memory: 21924kb
input:
fzztyyyfztzzfzyztftyfzyyzzzztyyfzttzttztyzztyyyfyyftyfyfzzffyzffytttzttyzzftyfyfyftyyfzyzffyfyyzztzyyttyfyztfyfzyfzfzyftttfyyfyytzyyzfyyyzztfttzyyytzzffytyzyyyyfzfftftzzztyfftfzfzytftfttytfyzfytzfzztttttzzyztyftzzzfzfzfffttyztzfftfftyfyffztzyffttyyfyfzytytyyttfzzfyyytzzftzyyfftftyytyffzffztfytfyyyty...
output:
867833603
result:
ok 1 number(s): "867833603"
Test #6:
score: 0
Accepted
time: 4ms
memory: 21872kb
input:
xauxlgtqbsianlzjzglalnbtlujfrkfdqgczpmididmtamzeablrbrbjgtsdkzzcfhvcpdawqkrgdsereirlxbizhbsxlcbtgwwshekbhatqonvgupswcowythifpoubxkuoxuuisnzolzwektdcaouxbkhofvdqzmjulmhgqjxwzhgrzmorhqkgekntbzsxgvjtehfbterrhhjhqggzrqiqmcshzwpfoburpyfoehqgtitesyaekhlzcvxzdqmunyrlrhbrjoigdjzpcgptyoiowwnmqrxucxixxydurbdh...
output:
301464023
result:
ok 1 number(s): "301464023"
Test #7:
score: 0
Accepted
time: 16ms
memory: 22084kb
input:
tttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttt...
output:
816920406
result:
ok 1 number(s): "816920406"
Test #8:
score: 0
Accepted
time: 0ms
memory: 21936kb
input:
cxccxccccxccxccxcxxxccxxcxcxcxcxxcccxcxccccccxccccxccxcxcxxcxxcxcxxxcxcccxcxxxxxccxxcccxxccxxxccxccxxxxcxxccccxccxxcccxcccxxxccccxcxcxccccxxxxccxxxxxcxxxxxxcxxccxxcxcxcxxxxxcxxccxcxxxcccxcxxxccccccccxxxcccxcxxcxxxxccxxxcccccxcccxccccccxxcccxxcccxxxccxxcxccxcccxxxccxccxxxccxcxxxxccxxcxcxxcxxccxxxcxcx...
output:
206627037
result:
ok 1 number(s): "206627037"
Test #9:
score: 0
Accepted
time: 0ms
memory: 19876kb
input:
vmqvvbbmvmmmqqvqvmmbbvqbqvbmmbqmvvbmmmqvqvbvqqmvbbmmvmvqbvmqqbqvqqvmvmmbqvvbvmvbqmqqbqqqbqqmvvmmbvvvbvvvbmqqvbqbmvvmvqqvbqbvvvqmvvvmvqqmvqbmbvmvmqmmbmqqqbbmvqbqbbqqbmmvmmqqqvvvqqqqqmmvvvvqmvmmmmvmqmqbbvbvvqmmmqbbmvqvmvmqbqbbbmqbqbqmqbqmqbmvvqmmvbmmbvbqqvmmmbbmbbmvmmvbmqmqbbqqbqqbbqmbmmmqbqbmvbmvmmmm...
output:
460659355
result:
ok 1 number(s): "460659355"
Test #10:
score: 0
Accepted
time: 0ms
memory: 19788kb
input:
xthikaxiescbqjzrpgtcpigqjsojlsxsiowkkzsdsgscoolhdtglvpgcoggzqnnjmocvanrogbzqjcmijoukjicadaakehxgjphjgnskjvfneoyaucfadilscsucjgweuzcdfapfnrfffdowxvzkvgqzmtszjldylvehzjlvmhproaehqhuwdoadenqdrqwrlxxfouzqolwbopmkpjshczocnnsxktxozahzwqpwbmvexguvjhbvbjwsdtgaitoqwsfzkwnzgeidkamgcfhzhitfxenunlcsbsesbczvmmbu...
output:
906223232
result:
ok 1 number(s): "906223232"
Test #11:
score: -100
Time Limit Exceeded
input:
bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb...