結果

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

ソースコード

diff # 

import sys

# ref: https://qiita.com/izu_nori/items/1c5cdef0500ffa0276f5
MOD = 998244353 # : 119*2**23+1
K,M,W = 119, 23, 31 # W : 2のM乗根

class NTT:
    def __init__(self):
        # ws[i] = 1の2^i乗根　　(31**(2**23) = 1 mod 998244353)
        # 内部で pow(W, 2**i, MOD) を計算
        self.ws = [pow(W, 1 << i, MOD) for i in range(M, -1, -1)]
        # inverse of ws
        self.iws = [pow(w, MOD - 2, MOD) for w in self.ws]

    def polymul_ntt(self, f, g):
        nf = len(f)
        ng = len(g)
        m = nf + ng - 1
        n = 2**(m - 1).bit_length()
        
        # 0-padding
        # C++版とは異なり、ここでMODをとる
        f = [x % MOD for x in f] + [0] * (n - nf) 
        g = [x % MOD for x in g] + [0] * (n - ng) 
        
        self.ntt(f)
        self.ntt(g)
        
        for i in range(n):
            f[i] = f[i] * g[i] % MOD
            
        self.intt(f)
        return f[:m]

    def ntt(self, A):
        if len(A) == 1: return
        n = len(A)
        k = n.bit_length() - 1
        r = 1 << (k - 1)
        
        # self.ws[k:0:-1] のスライスは [ws[k], ws[k-1], ..., ws[1]] を意味する
        for w in self.ws[k:0:-1]:
            for l in range(0, n, 2 * r):
                wi = 1
                for i in range(r): # Gentleman-Sade butterfly
                    A[l + i], A[l + i + r] = (A[l + i] + A[l + i + r]) % MOD, (A[l + i] - A[l + i + r]) * wi % MOD
                    wi = wi * w % MOD
            r = r // 2

    def intt(self, A):
        if len(A) == 1: return
        n = len(A)
        k = (n - 1).bit_length()
        r = 1
        
        # self.iws[1:k+1] のスライスは [iws[1], iws[2], ..., iws[k]] を意味する
        for w in self.iws[1:k + 1]:
            for l in range(0, n, 2 * r):
                wi = 1
                for i in range(r): # Colley-Tukey butterfly
                    A[l + i], A[l + i + r] = (A[l + i] + A[l + i + r] * wi) % MOD, (A[l + i] - A[l + i + r] * wi) % MOD
                    wi = wi * w % MOD
            r = r * 2
            
        ni = pow(n, MOD - 2, MOD)
        for i in range(n):
            A[i] = A[i] * ni % MOD

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

def main():
    # 高速入力を設定
    input = sys.stdin.readline
    
    # NTTソルバーをインスタンス化
    ntt_solver = NTT()
    
    n, m = map(int, input().split())

    # f[t] のリスト (生の値のリストとして持つ)
    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
        # このNTTクラスはリストをインプレース変更しない（内部でコピー/パディングする）
        # ため、f[t] を2回渡しても安全
        f_t_squared = ntt_solver.polymul_ntt(f[t], f[t])
        
        len_t = len(f[t])
        len_sq = len(f_t_squared)

        # C++版のロジックに合わせる
        # f[t+1] = f_t_squared (結果は十分な長さがある)
        f_tplus1 = f_t_squared[:] # コピー
        
        # f[t] の方が長い場合も考慮（この問題では発生しないが安全のため）
        if len_t > len_sq:
            f_tplus1.extend([0] * (len_t - len_sq))
            
        # f[t+1] = f_t_squared + f[t]
        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)! = k! を掛ける
    for i in range(1, k + 1):
        ans = (ans * i) % MOD

    print(ans)

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