結果

問題 No.3055 Simple Chicken Game
ユーザー suisen
提出日時 2025-01-18 16:10:14
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 777 ms / 2,000 ms
コード長 2,551 bytes
コンパイル時間 706 ms
コンパイル使用メモリ 82,220 KB
実行使用メモリ 91,700 KB
最終ジャッジ日時 2025-02-05 00:27:39
合計ジャッジ時間 7,952 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

diff # 

# correct

D = (-1, 0, +1)

n, MOD = map(int, input().split())
inv2 = pow(2, MOD - 2, MOD)
inv4 = pow(4, MOD - 2, MOD)
f = [[[[0, 0] for _ in range(3)] for _ in range(n)] for _ in range(3)]
for start_d in D:
    fdp = f[start_d + 1]
    fdp[0][start_d + 1] = [1, 0]
    for i in range(n - 1):
        ndp = fdp[i + 1]
        for d in D:
            p, h = fdp[i][d + 1]
            if d < 0:
                # head
                ndp[d + 1][0] += p * inv2
                ndp[d + 1][1] += h * inv2 + p * inv2
                # tail
                ndp[d + 2][0] += p * inv2
                ndp[d + 2][1] += h * inv2
            elif d > 0:
                # nop
                ndp[d][0] += p
                ndp[d][1] += h
            else:
                # nop
                ndp[d][0] += p * inv2
                ndp[d][1] += h * inv2
                # head
                ndp[d + 1][0] += p * inv4
                ndp[d + 1][1] += h * inv4 + p * inv4
                # tail
                ndp[d + 2][0] += p * inv4
                ndp[d + 2][1] += h * inv4
        for d in D:
            ndp[d + 1][0] %= MOD
            ndp[d + 1][1] %= MOD

H = [[0] * n for _ in range(3)]
for start_d in D:
    for i in range(n):
        for end_d in D:
            H[start_d + 1][i] += f[start_d + 1][i][end_d + 1][1]
        H[start_d + 1][i] %= MOD

T = H

P = [[0, 1, 0]]

R = [1] * n
for s in range(n):
    r = n - 1 - s
    nxt_P = [[0, 0, 0] for _ in range(s + 2)]
    for x in range(s + 1):
        for d in D:
            z = x + d
            y = s - x - z
            p = P[x][d + 1]
            if p == 0:
                # skip invalid states (e.g. min(x,y,z)<0)
                continue
            if d == -1:
                # head
                R[s] += p * inv2 % MOD * y
                nxt_P[x][0] += p * inv2
                # tail
                R[s] += p * inv2 % MOD * (n - 1 - T[1][r])
                nxt_P[x][1] += p * inv2
            elif d == 1:
                # nop
                R[s] += p * (x + y + H[1][r])
                nxt_P[x + 1][1] += p
            else:
                # nop
                R[s] += p * inv2 % MOD * (x + y + H[0][r])
                nxt_P[x + 1][0] += p * inv2
                # head
                R[s] += p * inv4 % MOD * y
                nxt_P[x][1] += p * inv4
                # tail
                R[s] += p * inv4 % MOD * (n - 1 - T[2][r])
                nxt_P[x][2] += p * inv4
        for d in D:
            nxt_P[x][d + 1] %= MOD
        R[s] %= MOD
    P = nxt_P

print(*R)
0