MnZn求助
查看原帖
MnZn求助
310581
ethan0328楼主2023/9/20 21:19

刚学OI一周,求调代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=3e6+10,mod=998244353;
int n,nl,nr,z[N][2],f[N],pre[N];
string a,l,r;
void exkmp(int op,string s)
{
	int l=0,r=0,len=s.length();
	s=" "+s;
	z[1][op]=len;
	for(int i=2;i<=len;i++)
	{
		if(i<=r)
		{
			z[i][op]=min(z[i-l+1][op],r-i+1);
		}else
		{
			z[i][op]=0;
		}
		while(z[i][op]+i<=len&&s[z[i][op]+1]==s[z[i][op]+i])
		{
			z[i][op]++;
		}
		if(z[i][op]+i-1>r)
		{
			r=z[i][op]+i-1;
			l=i;
		}
	}
}
signed main()
{
	cin>>a>>l>>r;
	n=a.length();
	nl=l.length();
	nr=r.length();
	exkmp(0,l+a);
	exkmp(1,r+a);
	a=" "+a;
	l=" "+l;
	r=" "+r;
	f[0]=1;
	for(int i=0;i<=n;i++)
	{
		if(i>0)
		{
			pre[i]=(pre[i]+pre[i-1])%mod;
		}
		f[i]=(f[i]+pre[i])%mod;
		if(i==n)
		{
			break;
		}
		if(a[i+1]=='0')
		{
			if(nl==1&&l[1]=='0')
			{
				f[i+1]=(f[i+1]+f[i])%mod;
			}
			continue;
		}
		if(nl!=nr)
		{
			pre[i+nl+1]=(pre[i+nl+1]+f[i])%mod;
			pre[i+nr]=(pre[i+nr]-f[i]+mod)%mod;
			if(z[i+1+nl][0]==nl||a[i+z[i+1+nl][0]+1]>l[z[i+1+nl][0]+1])
			{
				f[i+nl]=(f[i+nl]+f[i])%mod;
			}
			if(z[i+1+nr][1]==nr||a[i+z[i+1+nr][1]+1]<r[z[i+1+nr][1]+1])
			{
				f[i+nr]=(f[i+nr]+f[i])%mod;
			}
		}else
		{
			if((z[i+1+nl][0]==nl||a[i+z[i+1+nl][0]+1]>l[z[i+1+nl][0]+1])&&(z[i+1+nr][1]==nr||a[i+z[i+1+nr][1]+1]<r[z[i+1+nr][1]+1]))
			{
				f[i+nl]=(f[i+nl]+f[i])%mod;
			}
		}
	}
	cout<<f[n];
}
2023/9/20 21:19
加载中...