Основное
 
 
Отправитель Задача Язык Вердикт Время Память Отослано Протест.  
43591877 Дорешивание:
QAQT
1051E - 25 GNU C++11 Полное решение 62 мс 29368 КБ 2018-09-30 06:09:02 2018-09-30 06:09:02
→ Исходный код
#include<bits/stdc++.h>
using namespace std;
const int N=2e6+7,mod=998244353;
int n,l1,l2,b[N],c[N],s[N],f,tf;
char a[N],l[N],r[N];
void calc(char*x,int len,int*t)
{
	for(int i=1,l=0,r=0;i<len;i++)
	{
		if(i<=r)t[i]=min(t[i-l],r-i+1);
		while(i+t[i]<len&&x[t[i]]==x[i+t[i]])t[i]++;
		if(r<i+t[i])l=i,r=i+t[i]-1;
	}
}
int main()
{
	scanf("%s%s%s",a,l,r);
	n=strlen(a);l1=strlen(l);l2=strlen(r);
	l[l1]=r[l2]='*';
	for(int i=0;i<n;i++)l[l1+i+1]=r[l2+i+1]=a[i];
	calc(l,n+l1+1,b);calc(r,n+l2+1,c);
	for(int i=0;i<l1;i++)s[i]=1;
	for(int i=l1;i<=n;i++)
	{
		int L,R;
		if(i<l2)L=-1;
		else if(c[i+1]==l2||r[c[i+1]]>=a[i-l2+c[i+1]])L=i-l2-1;
		else L=i-l2;
		if(b[i+1]==l1||l[b[i+1]]<=a[i-l1+b[i+1]])R=i-l1;
		else R=i-l1-1;
		if(R==-1||L>R);
		else if(L==-1)f=s[R];
		else f=(s[R]-s[L]+mod)%mod;
		if(l[0]=='0'&&l1==1)f=(f+tf)%mod,tf=0;
		s[i]=s[i-1];
		if(a[i]=='0')tf=f;
		else s[i]=(s[i]+f)%mod;
	}
	printf("%d",f);
}
?
Время: ? ms, память: ? КБ
Вердикт: ?
Ввод
?
Вывод участника
?
Ответ жюри
?
Комментарий чекера
?
Диагностика
?
Показать детали тестирования