Submission #20952833

---

Source Code Expand

import sys
import numpy as np
import numba
from numba import njit, b1, i1, i4, i8, f8

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

def from_read(dtype=np.int64):
    return np.fromstring(read().decode(), dtype=dtype, sep=' ')


def from_readline(dtype=np.int64):
    return np.fromstring(readline().decode(), dtype=dtype, sep=' ')

MOD = 998_244_353

@njit
def mpow(a, n):
    p = 1
    while n:
        if n & 1:
            p = p * a % MOD
        a = a * a % MOD
        n >>= 1
    return p


@njit
def fact_table(N=1 << 20):
    N += 1
    fact = np.empty(N, np.int64)
    fact[0] = 1
    for n in range(1, N):
        fact[n] = n * fact[n - 1] % MOD
    fact_inv = np.empty(N, np.int64)
    fact_inv[N - 1] = mpow(fact[N - 1], MOD - 2)
    for n in range(N - 1, 0, -1):
        fact_inv[n - 1] = fact_inv[n] * n % MOD
    inv = np.empty(N, np.int64)
    inv[0] = 0
    inv[1:] = fact[:-1] * fact_inv[1:] % MOD
    return fact, fact_inv, inv

@njit((i8, ) * 6, cache=True)
def main(H, W, x1, y1, x2, y2):
    if x1 > x2:
        x1, x2 = x2, x1
    if y1 > y2:
        y1, y2 = y2, y1

    fact, fact_inv, inv = fact_table()

    def P(n, k):
        return fact[4 - k] * fact[n - 4] % MOD * fact_inv[n - k] % MOD

    def mult(f, g):
        shape = (f.shape[0] + g.shape[0] - 1, f.shape[1] + g.shape[1] - 1)
        h = np.zeros(shape, np.int64)
        for i in range(len(f)):
            for j in range(len(g)):
                h[i + j] += ntt_convolve(roots, iroots, f[i], g[j])
        return h % MOD

    n = x2 - x1 + 2 + y2 - y1 + 2
    f = np.zeros((1, n + 1), np.int64)
    f[0, n] = 1

    for N in [x1 - 1, H - x2, y1 - 1, W - y2]:
        shape = (f.shape[0] + 1, f.shape[1] + N + 1)
        h = np.zeros(shape, np.int64)
        for i in range(f.shape[0]):
            a = f.shape[1]
            # (1-x)x^Ny 倍
            h[i + 1, N:a + N] += f[i]
            h[i + 1, N + 1:a + N + 1] -= f[i]
            # (1-x^N) 倍
            h[i, :a] += f[i]
            h[i, N:N + a] -= f[i]
        # 1-x で割る
        for i in range(len(h)):
            h[i] = np.cumsum(h[i])
        f = h[:, :-1] % MOD

    K, N = f.shape
    ans = 0
    for k in range(K):
        for n in range(N):
            ans += P(n, k) * f[k, n] % MOD
    return ans % MOD

print(main(*map(int, read().split())))

Submission Info

Judge Result