【CF 1051E】Vasya and Big Integers

原題連結：http://codeforces.com/problemset/problem/1051/E

這題大概瞪個一眼就會發現是DP了
但是問題在轉移，怎麼想都很容易TLE
總之如果列出轉移式的話，大概會長這樣

$\color{white}{\space dp[i]=\displaystyle\sum_{l\leq substring (j,i]\leq r} dp[j] \space}$

那就是要想辦法搜到滿足的$\color{white}{\space j \space}$的範圍，可以發現存在單調性，衝動之下可能就會想二分搜了

可以用hash來達成類似的動作，複雜度約為$\color{white}{\space O(nlogn) \space}$

但是hash容易被攻擊，$\color{white}{\space O(nlogn) \space}$又感覺怕怕的
有沒有一個優美又是$\color{white}{\space O(n) \space}$的解呢？
有！

觀察字串比大小時的動作，也就是找到兩個字串的$\color{white}{\space LCP \space}$再比較下一個字元的大小

仔細看了一下，找$\color{white}{\space LCP \space}$的動作都是發生在字串$\color{white}{\space l,r \space}$跟字串$\color{white}{\space a \space}$的每個元素開始比較
那如果能預處理這些東西的$\color{white}{\space LCP \space}$，不就能$\color{white}{\space O(1) \space}$定位了嗎？

當然這裡絕對不會把Suffix Array搬出來
Z-value就足夠了！
把字串$\color{white}{\space a \space}$分別接在$\color{white}{\space l,r \space}$後面求Z-value，就完成預處理$\color{white}{\space LCP \space}$了

那區間的DP值也只不過是做點前綴處理而已(要記得判掉前綴0，跟反處理掉單一個0的情況)
整體就完全是線性的$\color{white}{\space O(n) \space}$

附上code:

	#pragma GCC optimize("Ofast")
	#include <bits/stdc++.h>
	#define jizz ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	#define pb push_back
	#define F first
	#define S second
	#define MP make_pair
	#define ET cout << "\n"
	#define ALL(v) v.begin(),v.end()
	#define MEM(i,j) memset(i,j,sizeof i)
	#define DB(a,s,e) {for(int i=s;i<e;i++) cout << a[i] << " ";ET;}
	using namespace std;
	typedef long long ll;
	typedef pair<int,int> pii;
	typedef pair<ll,ll> pll;
	const ll MOD=998244353;
	string a,l,r;
	ll dp[1000001],sdp[1000001];
	int zl[2000005],zr[2000005];
	void Z_value(int *z,string s){
	int L=0,R=0;
	for(int i=1;i<s.size();i++){
	if(i>R){
	L=R=i;
	while(R<s.size() && s[R-L]==s[R]) ++R;
	z[i]=R-L;R--;
	}
	else{
	int k=i-L;
	if(z[k]<R-i+1) z[i]=z[k];
	else{
	L=i;
	while(R<s.size() && s[R-L]==s[R]) ++R;
	z[i]=R-L,R--;
	}
	}
	}
	}
	ll cal(ll l,ll r)
	{
	if(l>r) return 0;
	if(l==0) sdp[r];
	return (sdp[r]-sdp[l-1]+MOD)%MOD;
	}
	int main()
	{jizz
	int i,j,k,x,y,flag=0;
	cin >> a >> l >> r;
	if(l=="0") flag=1;
	Z_value(zr,r+"&"+a);
	Z_value(zl,l+"&"+a);
	sdp[0]=dp[0]=1;
	for(i=1;i<l.size() && i<=a.size();++i)
	sdp[i]=1;
	for(j=l.size()+1;i<r.size() && i<=a.size();++i,++j)
	{
	if(zl[j]==l.size()||l[zl[j]]<a[i-l.size()+zl[j]]) dp[i]=cal(0,i-l.size());
	else dp[i]=cal(0,i-l.size()-1);
	if(flag&&a[i-1]=='0') dp[i]=(dp[i]+dp[i-1])%MOD;
	if(i==a.size()||a[i]!='0') sdp[i]=(sdp[i-1]+dp[i])%MOD;
	else sdp[i]=sdp[i-1];
	}
	for(k=r.size()+1;i<=a.size();++i,++j,++k)
	{
	if(zl[j]==l.size()||l[zl[j]]<a[i-l.size()+zl[j]]) y=i-l.size();
	else y=i-l.size()-1;
	if(zr[k]==r.size()||r[zr[k]]>a[i-r.size()+zr[k]]) x=i-r.size();
	else x=i-r.size()+1;
	dp[i]=cal(x,y);
	if(flag&&a[i-1]=='0') dp[i]=(dp[i]+dp[i-1])%MOD;
	if(i==a.size()||a[i]!='0') sdp[i]=(sdp[i-1]+dp[i])%MOD;
	else sdp[i]=sdp[i-1];
	}
	cout << dp[a.size()] << "\n";
	}

view raw gistfile1.txt hosted with ❤ by GitHub