Tiles (Codeforces 1473G)
Tags: Math, fft

Consider a road consisting of several rows. Each row is divided into several rectangular tiles, and all tiles in the same row are equal. The first row contains exactly one rectangular tile. Look at the picture below which shows how the tiles are arranged.The road is constructed as follows:   the first row consists of $$$1$$$ tile;  then $$$a_1$$$ rows follow; each of these rows contains $$$1$$$ tile greater than the previous row;  then $$$b_1$$$ rows follow; each of these rows contains $$$1$$$ tile less than the previous row;  then $$$a_2$$$ rows follow; each of these rows contains $$$1$$$ tile greater than the previous row;  then $$$b_2$$$ rows follow; each of these rows contains $$$1$$$ tile less than the previous row;  ...  then $$$a_n$$$ rows follow; each of these rows contains $$$1$$$ tile greater than the previous row;  then $$$b_n$$$ rows follow; each of these rows contains $$$1$$$ tile less than the previous row.   An example of the road with $$$n = 2$$$, $$$a_1 = 4$$$, $$$b_1 = 2$$$, $$$a_2 = 2$$$, $$$b_2 = 3$$$. Rows are arranged from left to right. You start from the only tile in the first row and want to reach the last row (any tile of it). From your current tile, you can move to any tile in the next row which touches your current tile.Calculate the number of different paths from the first row to the last row. Since it can be large, print it modulo $$$998244353$$$.

Input: The first line contains one integer $$$n$$$ ($$$1 \le n \le 1000$$$).Then $$$n$$$ lines follow. The $$$i$$$-th of them contains two integers $$$a_i$$$ and $$$b_i$$$ ($$$1 \le a_i, b_i \le 10^5$$$; $$$|a_i - b_i| \le 5$$$).Additional constraint on the input: the sequence of $$$a_i$$$ and $$$b_i$$$ never results in a row with non-positive number of tiles.

Output: Print one integer — the number of paths from the first row to the last row, taken modulo $$$998244353$$$.


Sample Inputs:
2
4 2
2 3

3
4 1
2 3
3 1

8
328 323
867 868
715 718
721 722
439 435
868 870
834 834
797 796

Sample Outputs:
850

10150

759099319

Solution (Python):
import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
mod = 998244353
r = [pow(3, mod >> i, mod) for i in range(23)]
ir = [pow(i, mod - 2, mod) for i in r]
u = [0] * (1 << 23)

def convolve(f, g, p):
    (lf, lg) = (len(f), len(g))
    c = lf + lg - 1
    x = c.bit_length()
    l = 1 << x
    for i in range(lf):
        u[i] = f[i]
    for i in range(lf, l):
        u[i] = 0
    for i in range(lg):
        u[i ^ l] = g[i]
    for i in range(lg, l):
        u[i ^ l] = 0
    m = l >> 1
    if not p:
        for k in range(x, 0, -1):
            r0 = r[k]
            for i in range(0, l, m << 1):
                y = 1
                for j in range(i, m + i):
                    (u[j], u[j + m]) = ((u[j] + u[j + m]) % mod, (u[j] - u[j + m]) * y % mod)
                    (u[j + l], u[j + m + l]) = ((u[j + l] + u[j + m + l]) % mod, (u[j + l] - u[j + m + l]) * y % mod)
                    y = y * r0 % mod
            m >>= 1
        for i in range(l):
            u[i] = u[i] * u[i ^ l] % mod
    else:
        for k in range(x, 0, -1):
            r0 = r[k]
            for i in range(0, l, m << 1):
                y = 1
                for j in range(i, m + i):
                    (u[j], u[j + m]) = ((u[j] + u[j + m]) % mod, (u[j] - u[j + m]) * y % mod)
                    y = y * r0 % mod
            m >>= 1
        for i in range(l):
            u[i] = u[i] * u[i] % mod
    m = 1
    for k in range(1, x + 1):
        r0 = ir[k]
        for i in range(0, l, m << 1):
            y = 1
            for j in range(i, m + i):
                (u[j], u[j + m]) = ((u[j] + u[j + m] * y) % mod, (u[j] - u[j + m] * y) % mod)
                y = y * r0 % mod
        m <<= 1
    (ans, im) = ([0] * c, pow(m, mod - 2, mod))
    for i in range(c):
        ans[i] = u[i] * im % mod
    return ans

def comb(n, r):
    return fact[n] * inv[r] % mod * inv[n - r] % mod if n >= r >= 0 else 0
n = int(input())
mod = 998244353
l = 2 * pow(10, 5) + 5
fact = [1] * (l + 1)
for i in range(1, l + 1):
    fact[i] = i * fact[i - 1] % mod
inv = [1] * (l + 1)
inv[l] = pow(fact[l], mod - 2, mod)
for i in range(l - 1, -1, -1):
    inv[i] = (i + 1) * inv[i + 1] % mod
dp = [1]
m = 1
for _ in range(n):
    (a, b) = map(int, input().split())
    m0 = m
    m += a - b
    l0 = max(a - m + 1, 0)
    r0 = a + b - l0
    x = [comb(a + b, i) for i in range(l0, r0 + 1)]
    v = convolve(dp, x, 0)
    l0 = (len(v) - m) // 2
    r0 = len(v) - l0
    dp = v[l0:r0]
ans = sum(dp) % mod
print(ans)

Solution (Python):
import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
mod = 998244353
r = [pow(3, mod >> i, mod) for i in range(23)]
ir = [pow(i, mod - 2, mod) for i in r]
u = [0] * (1 << 23)

def convolve(f, g, p):
    (lf, lg) = (len(f), len(g))
    c = lf + lg - 1
    x = c.bit_length()
    l = 1 << x
    for i in range(lf):
        u[i] = f[i]
    for i in range(lf, l):
        u[i] = 0
    for i in range(lg):
        u[i ^ l] = g[i]
    for i in range(lg, l):
        u[i ^ l] = 0
    m = l >> 1
    if not p:
        for k in range(x, 0, -1):
            r0 = r[k]
            for i in range(0, l, m << 1):
                y = 1
                for j in range(i, m + i):
                    (u[j], u[j + m]) = ((u[j] + u[j + m]) % mod, (u[j] - u[j + m]) * y % mod)
                    (u[j + l], u[j + m + l]) = ((u[j + l] + u[j + m + l]) % mod, (u[j + l] - u[j + m + l]) * y % mod)
                    y = y * r0 % mod
            m >>= 1
        for i in range(l):
            u[i] = u[i] * u[i ^ l] % mod
    else:
        for k in range(x, 0, -1):
            r0 = r[k]
            for i in range(0, l, m << 1):
                y = 1
                for j in range(i, m + i):
                    (u[j], u[j + m]) = ((u[j] + u[j + m]) % mod, (u[j] - u[j + m]) * y % mod)
                    y = y * r0 % mod
            m >>= 1
        for i in range(l):
            u[i] = u[i] * u[i] % mod
    m = 1
    for k in range(1, x + 1):
        r0 = ir[k]
        for i in range(0, l, m << 1):
            y = 1
            for j in range(i, m + i):
                (u[j], u[j + m]) = ((u[j] + u[j + m] * y) % mod, (u[j] - u[j + m] * y) % mod)
                y = y * r0 % mod
        m <<= 1
    (ans, im) = ([0] * c, pow(m, mod - 2, mod))
    for i in range(c):
        ans[i] = u[i] * im % mod
    return ans

def comb(n, r):
    return fact[n] * inv[r] % mod * inv[n - r] % mod if n >= r >= 0 else 0
n = int(input())
mod = 998244353
l = 2 * pow(10, 5) + 5
fact = [1] * (l + 1)
for i in range(1, l + 1):
    fact[i] = i * fact[i - 1] % mod
inv = [1] * (l + 1)
inv[l] = pow(fact[l], mod - 2, mod)
for i in range(l - 1, -1, -1):
    inv[i] = (i + 1) * inv[i + 1] % mod
dp = [1]
m = 1
for _ in range(n):
    (a, b) = map(int, input().split())
    m0 = m
    m += a - b
    l0 = max(a - m + 1, 0)
    r0 = a + b - l0
    x = [comb(a + b, i) for i in range(l0, r0 + 1)]
    v = convolve(dp, x, 0)
    l0 = (len(v) - m) // 2
    r0 = len(v) - l0
    dp = v[l0:r0]
ans = sum(dp) % mod
print(ans)

Solution (Python):
import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
MOD = 998244353
IMAG = 911660635
IIMAG = 86583718
rate2 = (0, 911660635, 509520358, 369330050, 332049552, 983190778, 123842337, 238493703, 975955924, 603855026, 856644456, 131300601, 842657263, 730768835, 942482514, 806263778, 151565301, 510815449, 503497456, 743006876, 741047443, 56250497, 867605899, 0)
irate2 = (0, 86583718, 372528824, 373294451, 645684063, 112220581, 692852209, 155456985, 797128860, 90816748, 860285882, 927414960, 354738543, 109331171, 293255632, 535113200, 308540755, 121186627, 608385704, 438932459, 359477183, 824071951, 103369235, 0)
rate3 = (0, 372528824, 337190230, 454590761, 816400692, 578227951, 180142363, 83780245, 6597683, 70046822, 623238099, 183021267, 402682409, 631680428, 344509872, 689220186, 365017329, 774342554, 729444058, 102986190, 128751033, 395565204, 0)
irate3 = (0, 509520358, 929031873, 170256584, 839780419, 282974284, 395914482, 444904435, 72135471, 638914820, 66769500, 771127074, 985925487, 262319669, 262341272, 625870173, 768022760, 859816005, 914661783, 430819711, 272774365, 530924681, 0)

def butterfly_base4(a):
    n = len(a)
    h = (n - 1).bit_length()
    le = 0
    while le < h:
        if h - le == 1:
            p = 1 << h - le - 1
            rot = 1
            for s in range(1 << le):
                offset = s << h - le
                for i in range(p):
                    l = a[i + offset]
                    r = a[i + offset + p] * rot
                    a[i + offset] = (l + r) % MOD
                    a[i + offset + p] = (l - r) % MOD
                rot *= rate2[(~s & -~s).bit_length()]
                rot %= MOD
            le += 1
        else:
            p = 1 << h - le - 2
            rot = 1
            for s in range(1 << le):
                rot2 = rot * rot % MOD
                rot3 = rot2 * rot % MOD
                offset = s << h - le
                for i in range(p):
                    a0 = a[i + offset]
                    a1 = a[i + offset + p] * rot
                    a2 = a[i + offset + p * 2] * rot2
                    a3 = a[i + offset + p * 3] * rot3
                    a1na3imag = (a1 - a3) % MOD * IMAG
                    a[i + offset] = (a0 + a2 + a1 + a3) % MOD
                    a[i + offset + p] = (a0 + a2 - a1 - a3) % MOD
                    a[i + offset + p * 2] = (a0 - a2 + a1na3imag) % MOD
                    a[i + offset + p * 3] = (a0 - a2 - a1na3imag) % MOD
                rot *= rate3[(~s & -~s).bit_length()]
                rot %= MOD
            le += 2

def butterfly_inv_base4(a):
    n = len(a)
    h = (n - 1).bit_length()
    le = h
    while le:
        if le == 1:
            p = 1 << h - le
            irot = 1
            for s in range(1 << le - 1):
                offset = s << h - le + 1
                for i in range(p):
                    l = a[i + offset]
                    r = a[i + offset + p]
                    a[i + offset] = (l + r) % MOD
                    a[i + offset + p] = (l - r) * irot % MOD
                irot *= irate2[(~s & -~s).bit_length()]
                irot %= MOD
            le -= 1
        else:
            p = 1 << h - le
            irot = 1
            for s in range(1 << le - 2):
                irot2 = irot * irot % MOD
                irot3 = irot2 * irot % MOD
                offset = s << h - le + 2
                for i in range(p):
                    a0 = a[i + offset]
                    a1 = a[i + offset + p]
                    a2 = a[i + offset + p * 2]
                    a3 = a[i + offset + p * 3]
                    a2na3iimag = (a2 - a3) * IIMAG % MOD
                    a[i + offset] = (a0 + a1 + a2 + a3) % MOD
                    a[i + offset + p] = (a0 - a1 + a2na3iimag) * irot % MOD
                    a[i + offset + p * 2] = (a0 + a1 - a2 - a3) * irot2 % MOD
                    a[i + offset + p * 3] = (a0 - a1 - a2na3iimag) * irot3 % MOD
                irot *= irate3[(~s & -~s).bit_length()]
                irot %= MOD
            le -= 2

def multiply(s, t):
    n = len(s)
    m = len(t)
    if min(n, m) <= 60:
        a = [0] * (n + m - 1)
        for i in range(n):
            if i % 8 == 0:
                for j in range(m):
                    a[i + j] += s[i] * t[j]
                    a[i + j] %= MOD
            else:
                for j in range(m):
                    a[i + j] += s[i] * t[j]
        return a.copy()
    a = s.copy()
    b = t.copy()
    z = 1 << (n + m - 2).bit_length()
    a += [0] * (z - n)
    b += [0] * (z - m)
    butterfly_base4(a)
    butterfly_base4(b)
    for i in range(z):
        a[i] *= b[i]
        a[i] %= MOD
    butterfly_inv_base4(a)
    a = a[:n + m - 1]
    iz = pow(z, MOD - 2, MOD)
    return [v * iz for v in a]

def comb(n, r):
    return fact[n] * inv[r] % mod * inv[n - r] % mod if n >= r >= 0 else 0
n = int(input())
mod = 998244353
l = 2 * pow(10, 5) + 5
fact = [1] * (l + 1)
for i in range(1, l + 1):
    fact[i] = i * fact[i - 1] % mod
inv = [1] * (l + 1)
inv[l] = pow(fact[l], mod - 2, mod)
for i in range(l - 1, -1, -1):
    inv[i] = (i + 1) * inv[i + 1] % mod
dp = [1]
m = 1
for _ in range(n):
    (a, b) = map(int, input().split())
    m0 = m
    m += a - b
    l0 = max(a - m + 1, 0)
    r0 = a + b - l0
    u = [comb(a + b, i) for i in range(l0, r0 + 1)]
    v = multiply(dp, u)
    l0 = (len(v) - m) // 2
    r0 = len(v) - l0
    dp = v[l0:r0]
ans = sum(dp) % mod
print(ans)