Submission #21369345

---

Source Code Expand

import sys
import numpy as np

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

MOD = 998_244_353

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=' ')

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] = pow(int(fact[N - 1]), -1, MOD)
    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

def fft_convolve(f, g):
    """
    数列 (多項式) f, g の畳み込みの計算．上下 15 bitずつ分けて計算することで，
    30 bit以下の整数，長さ 250000 程度の数列での計算が正確に行える．
    """
    Lf, Lg = f.shape[-1], g.shape[-1]
    L = Lf + Lg - 1
    fft_len = 1 << L.bit_length()
    fh, fl = f >> 15, f & (1 << 15) - 1
    gh, gl = g >> 15, g & (1 << 15) - 1

    Ffh = np.fft.rfft(fh, fft_len)
    Ffl = np.fft.rfft(fl, fft_len)
    Fgh = np.fft.rfft(gh, fft_len)
    Fgl = np.fft.rfft(gl, fft_len)

    a = np.rint(np.fft.irfft(Ffh * Fgh)).astype(np.int64) % MOD
    b = np.rint(np.fft.irfft(Ffh * Fgl + Ffl * Fgh)).astype(np.int64) % MOD
    c = np.rint(np.fft.irfft(Ffl * Fgl)).astype(np.int64) % MOD
    h = (a << 30) + (b << 15) + c
    return h[:L] % MOD

def main(N, M):
    fact, fact_inv, inv = fact_table(N + M + 10)
    C = fact[N] * fact_inv[:N + 1] % MOD * fact_inv[:N + 1][::-1] % MOD
    C = C[::2]
    C = np.append(C, np.zeros(M, np.int64))
    """
    和 → 数え
    """
    dp = np.ones(1, np.int64)
    dp[0] = 1
    while len(dp) <= M:
        newdp = np.zeros(2 * len(dp), np.int64)
        newdp[::2] = fft_convolve(dp, C[:len(dp)])[:len(dp)]
        dp = newdp
    return dp[M]

N, M = from_read()
print(main(N, M))

Submission Info

Judge Result