結果

問題 No.3174 勝ち残りじゃんけん
ユーザー t98slider
提出日時 2025-03-15 18:17:34
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 260 ms / 2,000 ms
コード長 2,757 bytes
コンパイル時間 478 ms
コンパイル使用メモリ 82,252 KB
実行使用メモリ 82,488 KB
最終ジャッジ日時 2025-03-15 18:17:40
合計ジャッジ時間 4,896 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 17
権限があれば一括ダウンロードができます

ソースコード

diff # 

#references: 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)
        self.ws = [pow(W,2**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()
        f = [x % MOD for x in f]+[0]*(n-nf) # 0-padding
        g = [x % MOD for x in g]+[0]*(n-ng) # 0-padding
        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, tws): # len(A) must be a power of 2
        if len(A) == 1:
            return A
        B0 = self._ntt(A[::2], tws) # 再帰計算
        B1 = self._ntt(A[1::2], tws)
        k = (len(A)-1).bit_length()
        res = [0]*len(A)
        r = 1<<(k-1)
        wi = 1
        w = tws[k]
        for i,(b0,b1) in enumerate(zip(B0,B1)): # バタフライ演算
            res[i] = (b0 + b1 * wi) % MOD
            res[i+r] = (b0 - b1 * wi) % MOD
            wi = (wi*w) % MOD
        return res
    def ntt(self, A):
        A[:] = self._ntt(A, self.ws)
    def intt(self, A):
        ni = pow(len(A), MOD-2, MOD)
        A[:] = [x*ni%MOD for x in  self._ntt(A, self.iws)] # 結果をinplaceに格納

ntt = NTT()

# 入力を受け取る
N = int(input())

# 階乗とその逆数を計算
fact = [0] * (N + 1)
inv = [0] * (N + 1)
fact[0] = 1
for i in range(1, N + 1, 1):
    fact[i] = (i * fact[i - 1]) % MOD
inv[N] = pow(fact[N], -1, MOD)
for i in range(N, 0, -1):
    inv[i - 1] = (inv[i] * i) % MOD

# あいこの場合の数を3で割ったものの逆数
coef = [0] * (N + 1)
pow2 = 2
for i in range(2, N + 1, 1):
    pow2 += pow2
    if pow2 >= MOD: pow2 -= MOD
    coef[i] = pow(pow2 - 2, -1, MOD)

# ちょうどN - i人になるときの確率とN - iの階乗とあいこの場合の数の逆数をかけたもの
dp = [0] * N
dp[0] = fact[N] * coef[N] % MOD

# オンラインNTT
for mid in range(1, N):
    Len = mid & -mid
    r = min(N, mid + Len)
    l = mid - Len
    A = [dp[i] for i in range(l, mid)]
    B = [inv[i] for i in range(r - l)]
    C = ntt.polymul_ntt(A, B)
    for i in range(mid, r):
        dp[i] += C[i - l]
    dp[mid] = (dp[mid] * coef[N - mid]) % MOD

# 答えを計算
ans = [0] * N
total, pow3, div3 = 0, pow(3, N - 1, MOD), (MOD + 1) // 3
for i in range(N):
    ans[N - 1 - i] = total
    total += (dp[i] * inv[N - i]) % MOD * pow3 % MOD
    if total >= MOD: total -= MOD
    pow3 *= div3
    pow3 %= MOD

# 答えを出力
print(*ans)
0