QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#200082 | #7512. Almost Prefix Concatenation | ucup-team1479# | WA | 142ms | 95572kb | C++17 | 3.0kb | 2023-10-04 15:18:40 | 2023-10-04 15:18:40 |
Judging History
answer
#include<bits/stdc++.h>
#define RI int
#define err puts("asd")
#define ll long long
#define ull unsigned long long
#define LL __int128
#define db double
#define mk make_pair
#define FL fflush(stdout)
#define eb emplace_back
#define FR(u,v) for(int i=h[u],v=a[i].t;i;i=a[i].n,v=a[i].t)
#define FB(x,z,y) for(int y=LG[(x)&-(x)],z=x;z;z^=z&-z,y=LG[z&-z])
#define FS(x,y) for(int y=x;y;y=(y-1)&x)
#define mem(a,b) memset(a,b,sizeof a)
#define yes puts("Yes")
#define no puts("No")
#define gg puts("-1")
#define vc vector
#define ex exit(0)
#define fi first
#define se second
#define int long long
//#pragma GCC optimize(2)
//#pragma GCC optimize(3)
using namespace std;
const db eps=1e-10;
const int inf=2e9+5;
const ll INF=1e18;
const int mod=998244353;
inline ll power(ll x,int y){
ll t=1;
while(y){
if(y&1) t=t*x%mod;
x=x*x%mod;y>>=1;
}
return t;
}
inline void gt(int &x,int &y){if(x>y) swap(x,y);}
inline void cmax(int &x,int y){x<y?x=y:0;}
inline void cmin(int &x,int y){x>y?x=y:0;}
inline void AD(int &x,int y){x+=y;if(x>=mod) x-=mod;}
inline ll read(){
ll s=0;char c=getchar();bool f=0;
while(c<'0'||c>'9'){if(c=='-') f=1;c=getchar();}
while(c>='0'&&c<='9') s=(s<<1)+(s<<3)+c-48,c=getchar();
return f?-s:s;
}
const int N=2e6+5;
const int P=13331;
ll F[N],H[N],pw[N];
ll f[N],g[N],h[N],tong1[N],tong2[N],tong3[N],tmp1,tmp2,tmp3;
int n,m,R[N];
char s[N],t[N];
inline ull get1(int x,int y){
return ((F[y]-F[x-1]*pw[y-x+1])%mod+mod)%mod;
}
inline ull get2(int x,int y){
return ((H[y]-H[x-1]*pw[y-x+1])%mod+mod)%mod;
}
signed main(){
ll op,x=0,y=0,z=0,u=0,v=0;
//freopen("1.in","r",stdin);
scanf("%s%s",s+1,t+1);
n=strlen(s+1);m=strlen(t+1);
pw[0]=1;
for(RI i=1;i<=n;++i) pw[i]=pw[i-1]*P%mod,F[i]=F[i-1]*P+s[i],F[i]%=mod;
for(RI i=1;i<=m;++i) pw[i]=pw[i-1]*P%mod,H[i]=H[i-1]*P+t[i],H[i]%=mod;
RI l,r,mid,pos;
for(RI i=1;i<=n;++i){
l=i,r=n;pos=i-1;
while(l<=r){
mid=l+r>>1;
if(get1(i,mid)==H[mid-i+1]) pos=mid,l=mid+1;
else r=mid-1;
}
//cout<<"A "<<pos<<endl;
x=l=pos+2;r=n;y=pos-i+3;pos=l-1;
while(l<=r){
mid=l+r>>1;
if(get1(x,mid)==get2(y,y-x+mid)) pos=mid,l=mid+1;
else r=mid-1;
}
R[i]=min(pos,n);
R[i]=min(R[i],i+m-1);
//cout<<R[i]<<endl;
}
h[0]=g[0]=1;
for(RI i=0;i<=n;++i){
AD(tmp1,tong1[i]);
AD(tmp2,tong2[i]);
AD(tmp3,tong3[i]);
if(i) f[i]=tmp1,g[i]=tmp2,h[i]=tmp3;
if(i!=n){
tong1[i+1]=(tong1[i+1]+f[i]+g[i])%mod;
tong2[i+1]=(tong2[i+1]+g[i]+h[i]*2)%mod;
tong3[i+1]=(tong3[i+1]+h[i])%mod;
tong1[R[i+1]+1]=(tong1[R[i+1]+1]-(f[i]+g[i])%mod+mod)%mod;
tong2[R[i+1]+1]=(tong2[R[i+1]+1]-(h[i]*2+g[i])%mod+mod)%mod;
tong3[R[i+1]+1]=(tong3[R[i+1]+1]-h[i]+mod)%mod;
}
/*for(RI j=i+1;j<=R[i+1];++j){
f[j]=(f[j]+f[i]+g[i])%mod;
g[j]=(g[j]+g[i]+h[i]*2)%mod;
h[j]=(h[j]+h[i])%mod;
}*/
}
cout<<f[n]<<endl;
return 0;
}
//颓入膏肓,没救了,有无神医相救?
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 16036kb
input:
ababaab aba
output:
473
result:
ok 1 number(s): "473"
Test #2:
score: 0
Accepted
time: 0ms
memory: 15912kb
input:
ac ccpc
output:
5
result:
ok 1 number(s): "5"
Test #3:
score: 0
Accepted
time: 0ms
memory: 16136kb
input:
qqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqq...
output:
75038697
result:
ok 1 number(s): "75038697"
Test #4:
score: 0
Accepted
time: 0ms
memory: 15992kb
input:
lvvvllvllvllvllllllllvvvllvlllvvlvlvllvlvvlvvvvlvvllllllvvlvlvvlllvvlvlvllllllvlvvvvvvlllvvvllvlvvvlvvlllvvvvvvlvlllvvvvlvvvvvlvvlvvlllvvllvvllvlvlvlvlvllllvvllvvllvlllvvvllllvvlvvllvvvvlvlvvlvvlllvvvvvvvvlvvlvlllvllvvvvllvvvlvvvvvvlvlllvllllvllllllllvvllllllvlvvlvvvlvllllvllvlvvllllllvlvvvlvlvlvvvl...
output:
538419149
result:
ok 1 number(s): "538419149"
Test #5:
score: 0
Accepted
time: 0ms
memory: 16072kb
input:
fzztyyyfztzzfzyztftyfzyyzzzztyyfzttzttztyzztyyyfyyftyfyfzzffyzffytttzttyzzftyfyfyftyyfzyzffyfyyzztzyyttyfyztfyfzyfzfzyftttfyyfyytzyyzfyyyzztfttzyyytzzffytyzyyyyfzfftftzzztyfftfzfzytftfttytfyzfytzfzztttttzzyztyftzzzfzfzfffttyztzfftfftyfyffztzyffttyyfyfzytytyyttfzzfyyytzzftzyyfftftyytyffzffztfytfyyyty...
output:
867833603
result:
ok 1 number(s): "867833603"
Test #6:
score: 0
Accepted
time: 0ms
memory: 15880kb
input:
xauxlgtqbsianlzjzglalnbtlujfrkfdqgczpmididmtamzeablrbrbjgtsdkzzcfhvcpdawqkrgdsereirlxbizhbsxlcbtgwwshekbhatqonvgupswcowythifpoubxkuoxuuisnzolzwektdcaouxbkhofvdqzmjulmhgqjxwzhgrzmorhqkgekntbzsxgvjtehfbterrhhjhqggzrqiqmcshzwpfoburpyfoehqgtitesyaekhlzcvxzdqmunyrlrhbrjoigdjzpcgptyoiowwnmqrxucxixxydurbdh...
output:
301464023
result:
ok 1 number(s): "301464023"
Test #7:
score: 0
Accepted
time: 0ms
memory: 16184kb
input:
tttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttt...
output:
816920406
result:
ok 1 number(s): "816920406"
Test #8:
score: 0
Accepted
time: 0ms
memory: 16132kb
input:
cxccxccccxccxccxcxxxccxxcxcxcxcxxcccxcxccccccxccccxccxcxcxxcxxcxcxxxcxcccxcxxxxxccxxcccxxccxxxccxccxxxxcxxccccxccxxcccxcccxxxccccxcxcxccccxxxxccxxxxxcxxxxxxcxxccxxcxcxcxxxxxcxxccxcxxxcccxcxxxccccccccxxxcccxcxxcxxxxccxxxcccccxcccxccccccxxcccxxcccxxxccxxcxccxcccxxxccxccxxxccxcxxxxccxxcxcxxcxxccxxxcxcx...
output:
206627037
result:
ok 1 number(s): "206627037"
Test #9:
score: 0
Accepted
time: 3ms
memory: 18040kb
input:
vmqvvbbmvmmmqqvqvmmbbvqbqvbmmbqmvvbmmmqvqvbvqqmvbbmmvmvqbvmqqbqvqqvmvmmbqvvbvmvbqmqqbqqqbqqmvvmmbvvvbvvvbmqqvbqbmvvmvqqvbqbvvvqmvvvmvqqmvqbmbvmvmqmmbmqqqbbmvqbqbbqqbmmvmmqqqvvvqqqqqmmvvvvqmvmmmmvmqmqbbvbvvqmmmqbbmvqvmvmqbqbbbmqbqbqmqbqmqbmvvqmmvbmmbvbqqvmmmbbmbbmvmmvbmqmqbbqqbqqbbqmbmmmqbqbmvbmvmmmm...
output:
460659355
result:
ok 1 number(s): "460659355"
Test #10:
score: 0
Accepted
time: 3ms
memory: 16272kb
input:
xthikaxiescbqjzrpgtcpigqjsojlsxsiowkkzsdsgscoolhdtglvpgcoggzqnnjmocvanrogbzqjcmijoukjicadaakehxgjphjgnskjvfneoyaucfadilscsucjgweuzcdfapfnrfffdowxvzkvgqzmtszjldylvehzjlvmhproaehqhuwdoadenqdrqwrlxxfouzqolwbopmkpjshczocnnsxktxozahzwqpwbmvexguvjhbvbjwsdtgaitoqwsfzkwnzgeidkamgcfhzhitfxenunlcsbsesbczvmmbu...
output:
906223232
result:
ok 1 number(s): "906223232"
Test #11:
score: 0
Accepted
time: 9ms
memory: 25980kb
input:
bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb...
output:
39285513
result:
ok 1 number(s): "39285513"
Test #12:
score: 0
Accepted
time: 14ms
memory: 24160kb
input:
hghggghghhghhgghgggghhghhhgghggghghhhhghghgggghhggggghhgghggghhhghggghghghggghggghgghhhghgggghghghgggghhhhhgghhgghhhghhghhhghhhhhhghghhgggggghghgggghghhghhgghhghhhhhhghgghhghghgggghgggggghghhhhhghhhhhhhgghhggggghhgghhhhhhhhghggggggghhghhghhghhgghhghgghhhhgghghghhhhhghggghhhhhhhgggggghgghghhhhghhgggg...
output:
58618935
result:
ok 1 number(s): "58618935"
Test #13:
score: 0
Accepted
time: 15ms
memory: 25656kb
input:
nnttcybbmnrnsuybrkmkmtumcyuyrrmbtybutunsyrkmunmncmkuknttmmtkymtcybttrmyrtckscttcksbtymtyukbbynnnbukttncmbutscbrytbrutnuyuknmtymckkttrrnsbtrkbnnnkbrccrcyybmnnybbkkbcbbccycsrcytnuucbbyytckrycktsmkymruycksrscytkskscbtbccbrurmumrkbkbttkcynmymbbmbkrksmnusryumsmmyrcsmusumbrkkbmsbyytmmruubskccsusnntcuntrrt...
output:
46252951
result:
ok 1 number(s): "46252951"
Test #14:
score: 0
Accepted
time: 15ms
memory: 25824kb
input:
ittaztseqcdirziayobnnxuzipvteycmgjbupnlxuheulnmzsdeymctprlxvkvzjwrotsauxagyrqcwzuwqyodrqsupwpyrmbwjqlvfdsrocneigxvnjfiseotxmutzwacfutqlmzmxwuqgjugwkafnxvzutgbrweqrdshwneksgxzzinnmbbioqdvbmavukaegvkpwauuoysklelsqhytlikpdpymbwhmbdmrycaiywtwjjqtecwoofyjhbumjtipwyopkuralejvopitpjcdswcvsugimgbrlibrteaqtb...
output:
838361918
result:
ok 1 number(s): "838361918"
Test #15:
score: 0
Accepted
time: 86ms
memory: 93840kb
input:
llllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllll...
output:
774442405
result:
ok 1 number(s): "774442405"
Test #16:
score: 0
Accepted
time: 140ms
memory: 92592kb
input:
nnnddndnndnddddndnnddnddnndddndndnnndnndndndnnnddndndnddnnddnndndndnnnndndddndnndndnndddndnnddnndndnnddnnddnddndddnnnndnnndddnndnddnnnddndddnndnnndndndndnddnddnndddndddnnndddnnndnndnndnnnddnnddnndnnndnnnddnnddddnndnnddnndnnnddddnddnnndnnddddddndndnnnnndnnnndddddnddnnndddndnnddndnnnddddnndndnndndndnd...
output:
478212008
result:
ok 1 number(s): "478212008"
Test #17:
score: -100
Wrong Answer
time: 142ms
memory: 95572kb
input:
ievnetxypatirsocqrmgmhfxnkgzrscclietylohbcshjjxfmqhlxvebythkwllhjxwjngxbjeivttdgjttmyqgxsqotxueuvzrslcqpranaucprjmfczshtoqggczmbuwixllhnlcjhrvfixisvqdlxxmevucbvzolweshgvxeocppggthqkljyiszeqkpnybogisosqzdasfqgpuzudnnabwoqtrpxllqkxlbwsexwduvutufncthrmywlsqlccetggdflmgewzvhsmpyznzsxcftkoyfhgmgvliwxbywi...
output:
962519891
result:
wrong answer 1st numbers differ - expected: '702291108', found: '962519891'