[Codeforces] 1051F. The Shortest Statement

題目連結:https://codeforces.com/contest/1051/problem/F

---

煩人的題目，一開始看到題的時候，忘記字串可以$(N, O(logN))$比較大小，然後想了想，想出一個什麼suffix array上二分搜之類的超噁比大小作法XD
後來發現可以$O(logN)$比大小之後，又因為hash碰撞卡了一段時間，才發現我p, q打反XD
總之，這題應該可以想到一個簡單的DP狀態$dp[i]$代表把後i個弄好的方法數，哪也很明顯的如果$s_i \neq \text{'0'}$，那就是找到一個區間的$j(i \le j \leq n)$使得$L \leq s_i...s_j \leq R$然後明顯$dp[i]=\sum_{j} dp[j]$，因為我們顯然只能把$s_i$跟那些人接在一起，而若$s_i = \text{'0'}$的情況也類似，所以現在變成我們要找到那些j，不過很明顯可以發現若a跟b差不多大，那他們的位數應該也差不多，所以我們只要去比較位數差不多的那個substring，就可以得知他是不是比較大了。

#include <bits/stdc++.h>
using namespace std;

const int N = 1000000 + 5;

const int qs[] = {
	1002939109, 1020288887, 1028798297, 1038684299, 
	1041211027, 1051762951, 1058585963, 1063020809, 
	1094763083, 1106384353, 1120154459, 1140593173, 
	1147930723, 1172520109, 1183835981, 1187659051, 
	1241251303, 1247184097, 1255940849, 1272759031, 
	1287027493, 1288511629, 1294632499, 1312650799, 
	1314753281, 1320080669, 1321970357, 1333133947, 
	1337684419, 1353508067, 1358715989, 1364961029, 
	1366046831, 1376536367, 1381705499, 1410637769, 
	1411311571, 1422795043, 1437499801, 1495803851, 
	1511764363, 1526710979, 1538018089, 1542373769, 
	1545326953, 1549429633, 1556212739, 1575971759, 
	1586465261, 1608336427, 1609783001, 1620728569, 
	1643267081, 1652401603, 1656717203, 1660920671, 
	1666858577, 1669260361, 1670240317, 1678791131, 
	1685583143, 1725964619, 1734856421, 1743134179, 
	1761537223, 1774260193, 1778872889, 1781930609, 
	1803000149, 1814256623, 1834876331, 1839154463, 
	1840044389, 1843241713, 1856039431, 1868564531, 
	1868732623, 1884198443, 1884616807, 1885059541, 
	1909942399, 1914471137, 1923951707, 1925453197, 
	1937719153, 1954649041, 1958915237, 1970709803, 
	1979612177, 1980446837, 1989761941, 2007826547, 
	2008033571, 2011186739, 2039465081, 2039728567, 
	2093735719, 2116097521, 2123852629, 2140170259
};
const int ps[] = {
	179, 181, 191, 193, 197, 199, 211, 223, 227, 229,
	233, 239, 241, 251, 257, 263, 269, 271, 277, 281,
	283, 293, 307, 311, 313, 317, 331, 337, 347, 349,
	353, 359, 367, 373, 379, 383, 389, 397, 401, 409,
	419, 421, 431, 433, 439, 443, 449, 457, 461, 463,
	467, 479, 487, 491, 499, 503, 509, 521, 523, 541,
	547, 557, 563, 569, 571, 577, 587, 593, 599, 601,
	739, 743, 751, 757, 761, 769, 773, 787, 797, 809,
	811, 821, 823, 827, 829, 839, 853, 857, 859, 863,
	947, 953, 967, 971, 977, 983, 991, 997, 1009, 1013,
};

class Hash{
private:
	static int p, q;
	int sz, prefix[N];
	static int power[N];
	static inline int add(int x, int y){return x+y>=q?x+y-q:x+y;}
	static inline int sub(int x, int y){return x-y<0?x-y+q:x-y;}
	static inline int mul(int x, int y){return static_cast<int>(1LL*x*y%q);}
public:
	void init(const std::string &x){
		if(p == -1) p = ps[rand()%100];
		if(q == -1) q = qs[rand()%100];
		sz = static_cast<int>(x.size());
		prefix[0]=0;
		for(int i=1;i<=sz;i++) prefix[i]=add(mul(prefix[i-1], p), x[i-1]);
		if(!power[0]){
			power[0]=1;
			for(int i=1;i<=sz;i++) power[i]=mul(power[i-1], p);
		}
	}
	int query(int l, int r) const {
		// 1-base (l, r]
		return sub(prefix[r], mul(prefix[l], power[r-l]));
	}
};
int Hash::p=-1, Hash::q=-1, Hash::power[];
const int MOD = 998244353;

inline int add(int x, int y){return x+y>=MOD?x+y-MOD:x+y;}
inline int sub(int x, int y){return x-y<0?x-y+MOD:x-y;}
inline int equal(int,int,const Hash&);

Hash hh, hl, hr;
int dp[N], podp[N];

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	srand(time(NULL));
	string base, L, R; cin >> base >> L >> R;
	hh.init(base); hl.init(L); hr.init(R);
	bool iszr = (L=="0");
	int n = static_cast<int>(base.size()),
		nr = static_cast<int>(R.size()),
		nl = static_cast<int>(L.size());
	dp[n] = podp[n] = 1;
	for(int i=n-1;i>=0;i--){
		if(base[i]=='0'){
			dp[i] = iszr*dp[i+1];
		}else{
			int lbound=-1, rbound=n;
			if(i+nr<=n){
				int idx = equal(i, i+nr, hr);
				rbound = i+nr;
				if(idx < nr and base[i+idx]>R[idx]) rbound--;
			}
			if(i+nl<=n){
				int idx = equal(i, i+nl, hl);
				lbound = i+nl;
				if(idx < nl and base[i+idx]<L[idx]) lbound++;
			}
			// now base[i, rbound) >= R, base[i, lbound) >= L
			if(lbound != -1 and lbound <= n)
				dp[i] = sub(podp[lbound], podp[rbound+1]);
		}
		podp[i] = add(dp[i], podp[i+1]);
	}
	cout << dp[0] << '\n';
	return 0;
}


inline int equal(int l, int r, const Hash& h2){
	// 0-base base[l, l+max_len) == h2[0, max_len)
	// binary search for max_len @ [0, r-l+1)
	int d = 0, u = r-l+1;
	while(u-d > 1){
		int m = (u+d)>>1;
		if(hh.query(l, l+m)==h2.query(0, m))
			d = m;
		else u = m;
	}
	// return max_length
	return d;
}