QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#192242#7512. Almost Prefix Concatenationucup-team896#TL 16ms22084kbC++141.3kb2023-09-30 14:02:502023-09-30 14:02:50

Judging History

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

  • [2023-09-30 14:02:50]
  • 评测
  • 测评结果:TL
  • 用时:16ms
  • 内存:22084kb
  • [2023-09-30 14:02:50]
  • 提交

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...

output:


result: