結果

問題 No.3349 AtCoder Janken Train
コンテスト
ユーザー りすりす/TwoSquirrels
提出日時 2025-11-01 02:11:00
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 3,831 bytes
コンパイル時間 245 ms
コンパイル使用メモリ 82,408 KB
実行使用メモリ 54,024 KB
最終ジャッジ日時 2025-11-13 21:10:33
合計ジャッジ時間 3,853 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2 TLE * 1
other -- * 30
権限があれば一括ダウンロードができます

ソースコード

diff # 

# Converted by Gemini 2.5 Pro

import sys

# yukicoderの環境では atcoder ライブラリが使えないため、
# 必要なNTT（数論変換）と畳み込みのロジックをPythonで実装して含めます。

MOD = 998244353

def pow_mod(x, n, m=MOD):
    """
    m を法とする x^n のべき乗
    """
    if n == 0:
        return 1
    res = pow_mod(x * x % m, n // 2, m)
    if n % 2 == 1:
        res = res * x % m
    return res

def inv_mod(x, m=MOD):
    """
    m を法とする x のモジュラ逆数
    """
    return pow_mod(x, m - 2, m)

def ntt(a, n, inverse=False):
    """
    Number Theoretic Transform (NTT)
    """
    pr = 3  # 998244353 の原始根
    
    # ビットリバース
    for i in range(1, n):
        j = 0
        k = i
        l = n >> 1
        while l > 0:
            if k & 1:
                j += l
            k >>= 1
            l >>= 1
        if i < j:
            a[i], a[j] = a[j], a[i]

    # バタフライ演算
    b = 1
    while b < n:
        w = pow_mod(pr, (MOD - 1) // (2 * b))
        if inverse:
            w = inv_mod(w)
        
        k = 0
        while k < n:
            for j in range(b):
                s = a[k + j]
                t = a[k + j + b] * pow_mod(w, j) % MOD
                a[k + j] = (s + t) % MOD
                a[k + j + b] = (s - t + MOD) % MOD
            k += 2 * b
        b *= 2

    if inverse:
        n_inv = inv_mod(n)
        for i in range(n):
            a[i] = a[i] * n_inv % MOD
    return a

def convolution(a, b):
    """
    a と b の畳み込み (MOD = 998244353)
    """
    la = len(a)
    lb = len(b)
    if la == 0 or lb == 0:
        return []

    n = 1
    while n < la + lb - 1:
        n *= 2

    a_ntt = a + [0] * (n - la)
    b_ntt = b + [0] * (n - lb)

    ntt(a_ntt, n, inverse=False)
    ntt(b_ntt, n, inverse=False)

    c_ntt = [(a_ntt[i] * b_ntt[i]) % MOD for i in range(n)]

    ntt(c_ntt, n, inverse=True)

    return c_ntt[:la + lb - 1]

# --------------------------------------------
# メインロジック
# --------------------------------------------

def main():
    # 高速入力を設定
    input = sys.stdin.readline
    
    n, m = map(int, input().split())

    # f[t](x) = \sum_{i=0}^{2^t} (暖色先頭で暖色が i 人含まれる列の総数) x^i
    f = [[] for _ in range(n + 1)]

    # f[0](x) = x
    f[0] = [0, 1]

    for t in range(n):
        # f[t+1](x) = (f_t(x))^2 + f_t(x)
        
        # (f_t(x))^2
        f_t_squared = convolution(f[t], f[t])
        
        # f[t+1] = f_t_squared + f[t]
        len_t = len(f[t])
        len_sq = len(f_t_squared)

        # C++版のロジック:
        # f[t + 1] = atcoder::convolution(f[t], f[t]);
        # for (auto i : views::iota(0, ssize(f[t]))) {
        #   f[t + 1][i] += f[t][i];
        # }
        # convolution の結果は f[t] より必ず長いため、
        # f[t] の長さだけ
        
        f_tplus1 = f_t_squared[:] # コピー
        
        # f[t] の方が長い場合も考慮（この問題では発生しないが安全のため）
        if len_t > len_sq:
            f_tplus1.extend([0] * (len_t - len_sq))
            
        for i in range(len_t):
            f_tplus1[i] = (f_tplus1[i] + f[t][i]) % MOD
        
        f[t + 1] = f_tplus1

    # ([x^{2^n - m}](f_n(x) + 1)) m! (2^n - m)!
    
    k = (1 << n) - m
    
    ans = 0
    if k < len(f[n]):
        ans = f[n][k]

    # f_n(x) + 1 の「+1」の部分 (x^0 の係数)
    # k = 0 (つまり m = 2^n) の場合に +1 する
    if k == 0:
        ans = (ans + 1) % MOD

    # m! を掛ける
    for i in range(1, m + 1):
        ans = (ans * i) % MOD

    # (2^n - m)! を掛ける
    for i in range(1, k + 1):
        ans = (ans * i) % MOD

    print(ans)

if __name__ == "__main__":
    main()
0