?
# | 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 |
/* 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; }
?
?
?
?