Strange Addition (Codeforces 1380F)
Tags: DP, matrices

Let $$$a$$$ and $$$b$$$ be some non-negative integers. Let's define strange addition of $$$a$$$ and $$$b$$$ as following:  write down the numbers one under another and align them by their least significant digit;  add them up digit by digit and concatenate the respective sums together. Assume that both numbers have an infinite number of leading zeros.For example, let's take a look at a strange addition of numbers $$$3248$$$ and $$$908$$$:  You are given a string $$$c$$$, consisting of $$$n$$$ digits from $$$0$$$ to $$$9$$$. You are also given $$$m$$$ updates of form:   $$$x~d$$$ — replace the digit at the $$$x$$$-th position of $$$c$$$ with a digit $$$d$$$. Note that string $$$c$$$ might have leading zeros at any point of time.After each update print the number of pairs $$$(a, b)$$$ such that both $$$a$$$ and $$$b$$$ are non-negative integers and the result of a strange addition of $$$a$$$ and $$$b$$$ is equal to $$$c$$$.Note that the numbers of pairs can be quite large, so print them modulo $$$998244353$$$.

Input: The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n, m \le 5 \cdot 10^5$$$) — the length of the number $$$c$$$ and the number of updates.The second line contains a string $$$c$$$, consisting of exactly $$$n$$$ digits from $$$0$$$ to $$$9$$$.Each of the next $$$m$$$ lines contains two integers $$$x$$$ and $$$d$$$ ($$$1 \le x \le n$$$, $$$0 \le d \le 9$$$) — the descriptions of updates.

Output: Print $$$m$$$ integers — the $$$i$$$-th value should be equal to the number of pairs $$$(a, b)$$$ such that both $$$a$$$ and $$$b$$$ are non-negative integers and the result of a strange addition of $$$a$$$ and $$$b$$$ is equal to $$$c$$$ after $$$i$$$ updates are applied.Note that the numbers of pairs can be quite large, so print them modulo $$$998244353$$$.

Note: After the first update $$$c$$$ is equal to $$$14$$$. The pairs that sum up to $$$14$$$ are: $$$(0, 14)$$$, $$$(1, 13)$$$, $$$(2, 12)$$$, $$$(3, 11)$$$, $$$(4, 10)$$$, $$$(5, 9)$$$, $$$(6, 8)$$$, $$$(7, 7)$$$, $$$(8, 6)$$$, $$$(9, 5)$$$, $$$(10, 4)$$$, $$$(11, 3)$$$, $$$(12, 2)$$$, $$$(13, 1)$$$, $$$(14, 0)$$$.After the second update $$$c$$$ is equal to $$$11$$$.After the third update $$$c$$$ is equal to $$$01$$$.

Sample Inputs:
2 3
14
2 4
2 1
1 0

Sample Outputs:
15
12
2

Solution (Python):
from sys import stdin
import sys

class LazySegTree:

    def __init__(self, N, first):
        self.LV = (N - 1).bit_length()
        self.NO = 2 ** self.LV
        self.First = first
        self.data = [first] * (2 * self.NO)
        self.lazy = [None] * (2 * self.NO)

    def calc(self, l, r):
        return min(l, r)

    def gindex(self, l, r):
        L = l + self.NO
        R = r + self.NO
        lm = L // (L & -L) >> 1
        rm = R // (R & -R) >> 1
        while L < R:
            if R <= rm:
                yield R
            if L <= lm:
                yield L
            L >>= 1
            R >>= 1
        while L:
            yield L
            L >>= 1

    def propagates(self, *ids):
        for i in reversed(ids):
            v = self.lazy[i - 1]
            if v is None:
                continue
            self.lazy[2 * i - 1] = self.data[2 * i - 1] = self.lazy[2 * i] = self.data[2 * i] = v
            self.lazy[i - 1] = None

    def update(self, l, r, x):
        (*ids,) = self.gindex(l, r)
        self.propagates(*ids)
        L = self.NO + l
        R = self.NO + r
        while L < R:
            if R & 1:
                R -= 1
                self.lazy[R - 1] = self.data[R - 1] = x
            if L & 1:
                self.lazy[L - 1] = self.data[L - 1] = x
                L += 1
            L >>= 1
            R >>= 1
        for i in ids:
            self.data[i - 1] = self.calc(self.data[2 * i - 1], self.data[2 * i])

    def query(self, l, r):
        self.propagates(*self.gindex(l, r))
        L = self.NO + l
        R = self.NO + r
        s = self.First
        while L < R:
            if R & 1:
                R -= 1
                s = self.calc(s, self.data[R - 1])
            if L & 1:
                s = self.calc(s, self.data[L - 1])
                L += 1
            L >>= 1
            R >>= 1
        return s

def inverse(a, mod):
    return pow(a, mod - 2, mod)

def calc(tmpR):
    ret = dp[tmpR - Lside[tmpR]] * dnum[c[tmpR]]
    if tmpR - Lside[tmpR] > 0:
        ret += dp[tmpR - Lside[tmpR] - 1] * dnum[c[tmpR] + 10]
    return ret
mod = 998244353
(n, m) = map(int, stdin.readline().split())
c = list(stdin.readline()[:-1])
c = list(map(int, c))
c = [0] + c + [9]
dnum = [0] * 20
for i in range(10):
    for j in range(10):
        dnum[i + j] += 1
dp = [0] * (n + 10)
dp[0] = 1
for i in range(n + 8):
    dp[i + 1] += dp[i] * 2
    dp[i + 1] %= mod
    dp[i + 2] += dp[i] * 8
    dp[i + 2] %= mod
ST = LazySegTree(len(c), float('inf'))
Lside = [None] * len(c)
tmpR = None
ans = 1
for i in range(len(c) - 1, -1, -1):
    if c[i] != 1:
        if tmpR != None:
            ST.update(i + 1, tmpR + 1, tmpR)
            Lside[tmpR] = i + 1
            ans *= calc(tmpR)
            ans %= mod
        tmpR = i
print(ans * inverse(dnum[9], mod) % mod, file=sys.stderr)
anss = []
vvv = inverse(dnum[9], mod)
for loop in range(m):
    (x, d) = map(int, stdin.readline().split())
    if d == 1:
        if c[x] != 1:
            now = 1
            newR = ST.query(x + 1, x + 2)
            now *= inverse(calc(x) * calc(newR), mod)
            ST.update(Lside[x], x + 1, newR)
            c[x] = d
            Lside[newR] = Lside[x]
            now *= calc(newR)
            ans *= now
    elif c[x] != 1:
        now = 1
        now *= inverse(calc(x), mod)
        c[x] = d
        now *= calc(x)
        ans *= now
    else:
        now = 1
        oldR = ST.query(x, x + 1)
        now *= inverse(calc(oldR), mod)
        c[x] = d
        Lside[x] = Lside[oldR]
        Lside[oldR] = x + 1
        ST.update(Lside[x], x + 1, x)
        now *= calc(oldR) * calc(x)
        ans *= now
    ans %= mod
    anss.append(ans * vvv % mod)
print('\n'.join(map(str, anss)))

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

def matmul(k, i, j):
    (u1, u2, u3, u4) = (tree1[i], tree2[i], tree3[i], tree4[i])
    (v1, v2, v3, v4) = (tree1[j], tree2[j], tree3[j], tree4[j])
    tree1[k] = (u1 * v1 % mod + u2 * v3 % mod) % mod
    tree2[k] = (u1 * v2 % mod + u2 * v4 % mod) % mod
    tree3[k] = (u3 * v1 % mod + u4 * v3 % mod) % mod
    tree4[k] = (u3 * v2 % mod + u4 * v4 % mod) % mod
    return

def update(i):
    (u1, u2, u3, u4) = (c[i + 1] + 1, 0 if c[i] ^ 1 else 9 - c[i + 1], 1, 0)
    i += l1
    (tree1[i], tree2[i]) = (u1, u2)
    (tree3[i], tree4[i]) = (u3, u4)
    i //= 2
    while i:
        matmul(i, 2 * i + 1, 2 * i)
        i //= 2
    return
(n, m) = map(int, input().split())
mod = 998244353
c = [0] + list(input().rstrip())
for i in range(1, n + 1):
    c[i] -= 48
l1 = pow(2, n.bit_length())
l2 = 2 * l1
(tree1, tree2) = ([1] * l2, [0] * l2)
(tree3, tree4) = ([0] * l2, [1] * l2)
for i in range(n):
    (u1, u2, u3, u4) = (c[i + 1] + 1, 0 if c[i] ^ 1 else 9 - c[i + 1], 1, 0)
    (tree1[i + l1], tree2[i + l1]) = (u1, u2)
    (tree3[i + l1], tree4[i + l1]) = (u3, u4)
for i in range(l1 - 1, 0, -1):
    matmul(i, 2 * i + 1, 2 * i)
ans = []
for _ in range(m):
    (x, d) = map(int, input().split())
    c[x] = d
    update(x - 1)
    if x ^ n:
        update(x)
    ans0 = tree1[1]
    ans.append(ans0)
sys.stdout.write('\n'.join(map(str, ans)))

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

def matmul(k, i, j):
    (u1, u2, u3, u4) = (tree1[i], tree2[i], tree3[i], tree4[i])
    (v1, v2, v3, v4) = (tree1[j], tree2[j], tree3[j], tree4[j])
    tree1[k] = (u1 * v1 % mod + u2 * v3 % mod) % mod
    tree2[k] = (u1 * v2 % mod + u2 * v4 % mod) % mod
    tree3[k] = (u3 * v1 % mod + u4 * v3 % mod) % mod
    tree4[k] = (u3 * v2 % mod + u4 * v4 % mod) % mod
    return

def update(i):
    (u1, u2, u3, u4) = (c[i + 1] + 1, 0 if c[i] ^ 1 else 9 - c[i + 1], 1, 0)
    i += l1
    (tree1[i], tree2[i]) = (u1, u2)
    (tree3[i], tree4[i]) = (u3, u4)
    i //= 2
    while i:
        matmul(i, 2 * i + 1, 2 * i)
        i //= 2
    return
(n, m) = map(int, input().split())
mod = 998244353
c = [0] + list(input().rstrip())
for i in range(1, n + 1):
    c[i] -= 48
l1 = pow(2, n.bit_length())
l2 = 2 * l1
(tree1, tree2) = ([1] * l2, [0] * l2)
(tree3, tree4) = ([0] * l2, [1] * l2)
for i in range(n):
    (u1, u2, u3, u4) = (c[i + 1] + 1, 0 if c[i] ^ 1 else 9 - c[i + 1], 1, 0)
    (tree1[i + l1], tree2[i + l1]) = (u1, u2)
    (tree3[i + l1], tree4[i + l1]) = (u3, u4)
for i in range(l1 - 1, 0, -1):
    matmul(i, 2 * i + 1, 2 * i)
ans = []
for _ in range(m):
    (x, d) = map(int, input().split())
    c[x] = d
    update(x - 1)
    if x ^ n:
        update(x)
    ans0 = tree1[1]
    ans.append(ans0)
sys.stdout.write('\n'.join(map(str, ans)))