結果

問題 No.3190 Scoring
ユーザー Mitarushi
提出日時 2025-06-16 00:35:55
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 8,887 ms / 10,000 ms
コード長 2,781 bytes
コンパイル時間 449 ms
コンパイル使用メモリ 82,304 KB
実行使用メモリ 349,332 KB
最終ジャッジ日時 2025-06-27 01:28:30
合計ジャッジ時間 183,483 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 32
権限があれば一括ダウンロードができます

ソースコード

diff # 

mod = 998244353

frac_max = 5 * 10 ** 5
frac = [1] * (frac_max + 1)
for i in range(2, frac_max + 1):
    frac[i] = frac[i - 1] * i % mod
frac_inv = [1] * (frac_max + 1)
frac_inv[frac_max] = pow(frac[frac_max], mod - 2, mod)
for i in range(2, frac_max + 1)[::-1]:
    frac_inv[i - 1] = frac_inv[i] * i % mod

def fft(a):
    n = len(a)
    m = n
    while m >= 2:
        m2 = m // 2
        w = pow(3, (mod - 1) // m, mod)
        for i in range(0, n, m):
            wj = 1
            for j in range(m2):
                u = a[i + j]
                v = a[i + j + m2]
                a[i + j] = (u + v) % mod
                a[i + j + m2] = (u - v) * wj % mod
                wj = wj * w % mod
        m //= 2

def ifft(a):
    n = len(a)
    m = 2
    while m <= n:
        m2 = m // 2
        w = pow(3, mod - 1 - (mod - 1) // m, mod)
        for i in range(0, n, m):
            wj = 1
            for j in range(m2):
                u = a[i + j]
                v = a[i + j + m2] * wj
                a[i + j] = (u + v) % mod
                a[i + j + m2] = (u - v) % mod
                wj = wj * w % mod
        m *= 2

def convolution(a, b):
    n = len(a) + len(b) - 1
    m = 1 << (n - 1).bit_length()
    a = a + [0] * (m - len(a))
    b = b + [0] * (m - len(b))

    fft(a)
    fft(b)
    
    for i in range(m):
        a[i] = a[i] * b[i] % mod
    
    ifft(a)
    
    inv_m = pow(m, mod - 2, mod)
    return [x * inv_m % mod for x in a[:n]]


def add(a, b):
    size = max(len(a), len(b))
    c = [0] * size
    for i, x in enumerate(a):
        c[i] += x
    for i, x in enumerate(b):
        c[i] = (c[i] + x) % mod
    while c and c[-1] == 0:
        c.pop()
    return c

def inv(a, k):
    assert a[0] == 1
    a = a + [0] * (k - len(a))
    b = [1]
    n = 1
    while n < k:
        ab = convolution(a[:2 * n], b)
        d = [mod - ab[i] for i in range(n, 2 * n)]
        db = convolution(d, b)
        b = b + db[:n]
        n *= 2
    return b[:k]

n, s, m = map(int, input().split())
m2 = (m + 1) // 2

fm_tmp = convolution(
    [frac_inv[i] for i in range(m2, m + 1)],
    [frac_inv[i] if i % 2 == 0 else mod - frac_inv[i] for i in range(0, m + 1)]
)
fm = [fm_tmp[i - m2] * frac[m] * frac_inv[m - i] % mod for i in range(m2, m + 1)]

p = [frac[s - i + n - 1] * frac[s] * frac_inv[s - i] * frac_inv[s + n - 1] % mod for i in range(1, s + 1)]

prod = [([1], [1, mod - i]) for i in p]
i = 0
while i + 1 < len(prod):
    a1, b1 = prod[i]
    a2, b2 = prod[i + 1]
    b3 = convolution(b1, b2)
    a3 = add(
        convolution(a1, b2),
        convolution(a2, b1)
    )
    prod.append((a3, b3))
    i += 2

a, b = prod[-1]
ab = convolution(a, inv(b, m + 1))
ans = 0
for i in range(m2, m + 1):
    ans = (ans + ab[i] * fm[i - m2]) % mod
print(ans * n % mod)
0