General
 
 
# Author Problem Lang Verdict Time Memory Sent Judged  
54524276 Practice:
ArshiaDadras
1051E - 25 C++17 (GCC 7-32) Accepted 62 ms 29688 KB 2019-05-23 16:44:32 2019-05-23 16:44:32
→ Source
/* In the name of Allah */
#include<bits/stdc++.h>
using namespace std;

const int N = 1e6 + 10, P = 998244353;
int n, m[2], z[2][N + N], dp[N], w[N];
string a, b[2];

inline void read_input() {
	cin >> a >> b[0] >> b[1];
	m[0] = b[0].size();
	m[1] = b[1].size();
	n = a.size();
}

inline void solve() {
	for (int id = 0; id < 2; id++) {
		int sz = m[id] + n;
		string s = b[id] + a;
		for (int i = 1, p = 0; i < sz; i++) {
			z[id][i] = z[id][i - p];
			if (i - p + z[id][i] >= z[id][p]) {
				z[id][i] = max(p + z[id][p] - i, 0), p = i;
				while (p + z[id][p] < sz && s[z[id][p]] == s[p + z[id][p]])
					z[id][p]++;
			}
		}
	}
	for (int i = dp[1] = 1; i <= n; i++) {
		int st = i - m[0], x = z[0][i], en = i - m[1], y = z[1][i];
		if (st >= 0 && x < m[0] && a[st + x] < b[0][x])
			st--;
		if (en >= 0 && y < m[1] && a[en + y] > b[1][y])
			en++;
		w[i] = (st < 0 || st < en? 0: dp[++st] - dp[max(en, 0)]) % P;
		dp[i + 1] = (dp[i] + w[i]) % P;
		if (a[i - 1] == '0') {
			(dp[i] -= w[i - 1]) %= P;
			(dp[i + 1] -= w[i - 1]) %= P;
		}
	}
	cout << (2LL * P + dp[n + 1] - dp[n]) % P;
}

int main() {
	ios:: sync_with_stdio(0), cin.tie(0), cout.tie(0);
	read_input(), solve();
	return 0;
}
?
Time: ? ms, memory: ? KB
Verdict: ?
Input
?
Participant's output
?
Jury's answer
?
Checker comment
?
Diagnostics
?
Click to see test details