QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#200082#7512. Almost Prefix Concatenationucup-team1479#WA 142ms95572kbC++173.0kb2023-10-04 15:18:402023-10-04 15:18:40

Judging History

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

  • [2023-10-04 15:18:40]
  • 评测
  • 测评结果:WA
  • 用时:142ms
  • 内存:95572kb
  • [2023-10-04 15:18:40]
  • 提交

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;
}

//颓入膏肓,没救了,有无神医相救?








详细

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'