Основное
 
 
Отправитель Задача Язык Вердикт Время Память Отослано Протест.  
173278358 Дорешивание:
bkifhr9
1051E - 25 C++14 (GCC 6-32) Полное решение 62 мс 34256 КБ 2022-09-24 09:20:18 2022-09-24 09:20:18
→ Исходный код
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int mod=998244353;
const int N=1e6+5;
char a[N],l[N],r[N];
int la,ll,lr;
LL dp[N],d[N];

int lcp[2][N],z1[N],z2[N];

void get_z(char s[],int len,int z[]){
	int l=0,r=0;z[1]=len;
	for(int i=2;i<=len;i++){
		if(i<=r) z[i]=min(z[i-l+1],r-i+1);
		while(i+z[i]<=len&&s[i+z[i]]==s[z[i]+1]) z[i]++;
		if(i+z[i]-1>r) r=i+z[i]-1,l=i;
	}
}
void ex_kmp(char s[],int len,int z[],int p[]){
	int l=0,r=0;
	for(int i=1;i<=la;i++){
		if(i<=r) p[i]=min(z[i-l+1],r-i+1);
		while(i+p[i]<=la&&p[i]+1<=len&&a[i+p[i]]==s[p[i]+1]) p[i]++;
		if(i+p[i]-1>r) r=i+p[i]-1,l=i;
	}
}

int main(){
	scanf("%s%s%s",(a+1),(l+1),(r+1));
	la=strlen(a+1);ll=strlen(l+1);lr=strlen(r+1);
	get_z(l,ll,z1),get_z(r,lr,z2);
	ex_kmp(l,ll,z1,lcp[0]),ex_kmp(r,lr,z2,lcp[1]);
	
	dp[la+1]=d[la+1]=1;
	for(int i=la;i;i--){
		if(a[i]=='0') dp[i]=(l[1]=='0'?dp[i+1]:0);
		else{
			int st=i+ll-1,ed=i+lr-1;
			int x=lcp[0][i];
			if(x<ll&&a[i+x]<l[x+1]) st++;
			x=lcp[1][i];
			if(x<lr&&a[i+x]>r[x+1]) ed--;
			ed=min(ed,la);
			if(st>ed) dp[i]=0;
			else dp[i]=d[st+1]-d[ed+2];
		}
		dp[i]=(dp[i]+mod)%mod;
		d[i]=d[i+1]+dp[i];
		d[i]=(d[i]+mod)%mod;
	}
	printf("%lld",dp[1]);
	return 0;
}
				  	  							   	  					 			
?
Время: ? ms, память: ? КБ
Вердикт: ?
Ввод
?
Вывод участника
?
Ответ жюри
?
Комментарий чекера
?
Диагностика
?
Показать детали тестирования