Vasya and Big Integers (Codeforces 1051E)
Tags: DP, hashing

Vasya owns three big integers — $$$a, l, r$$$. Let's define a partition of $$$x$$$ such a sequence of strings $$$s_1, s_2, \dots, s_k$$$ that $$$s_1 + s_2 + \dots + s_k = x$$$, where $$$+$$$ is a concatanation of strings. $$$s_i$$$ is the $$$i$$$-th element of the partition. For example, number $$$12345$$$ has the following partitions: ["1", "2", "3", "4", "5"], ["123", "4", "5"], ["1", "2345"], ["12345"] and lots of others.Let's call some partition of $$$a$$$ beautiful if each of its elements contains no leading zeros.Vasya want to know the number of beautiful partitions of number $$$a$$$, which has each of $$$s_i$$$ satisfy the condition $$$l \le s_i \le r$$$. Note that the comparison is the integer comparison, not the string one.Help Vasya to count the amount of partitions of number $$$a$$$ such that they match all the given requirements. The result can be rather big, so print it modulo $$$998244353$$$.

Input: The first line contains a single integer $$$a~(1 \le a \le 10^{1000000})$$$.The second line contains a single integer $$$l~(0 \le l \le 10^{1000000})$$$.The third line contains a single integer $$$r~(0 \le r \le 10^{1000000})$$$.It is guaranteed that $$$l \le r$$$.It is also guaranteed that numbers $$$a, l, r$$$ contain no leading zeros.

Output: Print a single integer — the amount of partitions of number $$$a$$$ such that they match all the given requirements modulo $$$998244353$$$.

Note: In the first test case, there are two good partitions $$$13+5$$$ and $$$1+3+5$$$.In the second test case, there is one good partition $$$1+0+0+0+0$$$.

Sample Inputs:
135
1
15

10000
0
9

Sample Outputs:
2

1

Solution (Python):
import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def z_algorithm(w):
    m = len(w)
    z = [0] * m
    z[0] = m
    (i, j) = (1, 0)
    while i < m:
        while i + j < m and w[j] == w[i + j]:
            j += 1
        z[i] = j
        if not j:
            i += 1
            continue
        l = 1
        while l < j and l + z[l] < j:
            z[i + l] = z[l]
            l += 1
        i += l
        j -= l
    return z
a = list(input().rstrip())
l = list(input().rstrip())
r = list(input().rstrip())
if len(a) < len(l):
    ans = 0
    print(ans)
    exit()
if len(a) < len(r):
    r = list(a)
mod = 998244353
n = len(a)
(l0, r0) = (len(l), len(r))
for i in a:
    l.append(i)
for i in a:
    r.append(i)
zl = z_algorithm(l)
zr = z_algorithm(r)
dp = [0] * (n + 1)
dpsum = [0] * (n + 2)
(dp[0], dpsum[1]) = (1, 1)
(l1, r1) = (l0 + 1, r0 - 1)
ng = [0] * (n + 2)
for i in range(n):
    (u, v) = (i + 1 - r1, i + 1 - l1)
    if u <= v + 1:
        dp[i + 1] = (dpsum[v + 1] - dpsum[u]) % mod
        dp[i + 1] -= (ng[v + 1] - ng[u]) % mod
        dp[i + 1] %= mod
        if i >= l0 - 1:
            zli = zl[i + 1]
            if zli >= l0 or l[zli] <= a[i + zli - l0 + 1]:
                dp[i + 1] += dp[i - l0 + 1]
                dp[i + 1] %= mod
        if i >= r0 - 1:
            zri = zr[i + 1]
            if zri >= r0 or r[zri] >= a[i + zri - r0 + 1]:
                dp[i + 1] += dp[i - r0 + 1]
                dp[i + 1] %= mod
    elif i >= l0 - 1:
        zli = zl[i + 1]
        if zli >= l0 or l[zli] <= a[i + zli - l0 + 1]:
            zri = zr[i + 1]
            if zri >= r0 or r[zri] >= a[i + zri - r0 + 1]:
                dp[i + 1] += dp[i - l0 + 1]
                dp[i + 1] %= mod
    dpsum[i + 2] = (dp[i + 1] + dpsum[i + 1]) % mod
    if not a[i] ^ 48:
        ng[i + 1] += dp[i]
        dp[i] = 0
    ng[i + 2] += ng[i + 1]
    ng[i + 2] %= mod
ans = dp[n]
print(ans)

Solution (Python):
def kmp(pat, text, t):
    s = pat + '?' + text
    z = [0 for i in range(len(s))]
    L = 0
    R = 0
    n = len(s)
    for i in range(1, len(s)):
        if i > R:
            L = R = i
            while R < n and s[R - L] == s[R]:
                R += 1
            z[i] = R - L
            R -= 1
        elif z[i - L] + i <= R:
            z[i] = z[i - L]
        else:
            L = i
            while R < n and s[R - L] == s[R]:
                R += 1
            z[i] = R - L
            R -= 1
    for i in range(len(pat) + 1, len(z)):
        dp[t][i - (len(pat) + 1)] = z[i] % len(pat)
from sys import stdin
mod = 998244353
a = stdin.readline().strip()
l = stdin.readline().strip()
r = stdin.readline().strip()
x = len(l)
y = len(r)
n = len(a)
dp = [[0 for i in range(len(a))] for j in range(2)]
ans = [0 for i in range(len(a) + 1)]
ans[-1] = 1
kmp(l, a, 0)
kmp(r, a, 1)
auxl = x - 1
auxr = y - 1
acum = [0 for i in range(n + 2)]
acum[n] = 1
for i in range(n - 1, -1, -1):
    if a[i] == '0':
        if l[0] == '0':
            ans[i] = ans[i + 1]
        acum[i] = (acum[i + 1] + ans[i]) % mod
        continue
    if auxl >= n:
        acum[i] = (acum[i + 1] + ans[i]) % mod
        continue
    if auxl != auxr:
        if auxl + i < n and a[dp[0][i] + i] >= l[dp[0][i]]:
            ans[i] = (ans[i] + ans[i + auxl + 1]) % mod
        if auxr + i < n and a[dp[1][i] + i] <= r[dp[1][i]]:
            ans[i] = (ans[i] + ans[i + auxr + 1]) % mod
    elif auxl + i < n and a[dp[0][i] + i] >= l[dp[0][i]] and (a[dp[1][i] + i] <= r[dp[1][i]]):
        ans[i] = (ans[i] + ans[i + auxl + 1]) % mod
    lim1 = auxl + i + 2
    lim2 = min(auxr + i + 1, n + 1)
    if lim1 < lim2:
        ans[i] = (ans[i] + acum[lim1] - acum[lim2]) % mod
    acum[i] = (acum[i + 1] + ans[i]) % mod
print(ans[0] % mod)

Solution (Python):
def z_function(s):
    n = len(s)
    z = [0] * n
    (l, r) = (0, 0)
    for i in range(1, n):
        if i < r:
            z[i] = min(r - i, z[i - l])
        while i + z[i] < n and s[i + z[i]] == s[z[i]]:
            z[i] += 1
        if i + z[i] > r:
            (l, r) = (i, i + z[i])
    return z
MOD = 998244353

def solve():
    a = input()
    l = input()
    r = input()
    z_l = z_function(l + '-' + a)
    z_r = z_function(r + '-' + a)
    z_l = z_l[len(l) + 1:]
    z_r = z_r[len(r) + 1:]
    dp = [0] * (len(a) + 1)
    dp_sum = [0] * (len(a) + 1)
    dp[len(a)] = dp_sum[len(a)] = 1
    for i in range(len(a) - 1, -1, -1):
        if a[i] == '0':
            if l == '0':
                dp[i] = dp[i + 1]
            dp_sum[i] = (dp[i] + dp_sum[i + 1]) % MOD
            continue
        len_l = z_l[i]
        len_r = z_r[i]
        left = i + len(l)
        if len(a) - i < len(l) or (len_l < len(l) and int(a[i + len_l]) < int(l[len_l])):
            left += 1
        right = i + len(r)
        if len(a) - i >= len(r) and len_r < len(r) and (int(a[i + len_r]) > int(r[len_r])):
            right -= 1
        if left <= right and left <= len(a):
            dp[i] = dp_sum[left] - (dp_sum[right + 1] if right < len(a) else 0)
            dp[i] %= MOD
        dp_sum[i] = (dp[i] + dp_sum[i + 1]) % MOD
    print(dp[0])
solve()