結果

問題 No.3117 Reversible Tile
ユーザー keymoon
提出日時 2025-04-19 07:17:46
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 91 ms / 3,000 ms
コード長 1,250 bytes
コンパイル時間 361 ms
コンパイル使用メモリ 82,304 KB
実行使用メモリ 71,620 KB
最終ジャッジ日時 2025-04-19 07:17:50
合計ジャッジ時間 3,105 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 24
権限があれば一括ダウンロードができます

ソースコード

diff # 

# solved by ChatGPT o4-mini-high (really sorry)
MOD = 998244353

n, m = map(int, input().split())
A = list(map(int, input().split()))

s = 0
for i in range(n):
    if A[i] == 1 and (i == 0 or A[i-1] == 0):
        s += 1

P = n + 1

max_n = n + 1
fac = [1] * (max_n + 1)
for i in range(1, max_n + 1):
    fac[i] = fac[i-1] * i % MOD
invfac = [1] * (max_n + 1)
invfac[max_n] = pow(fac[max_n], MOD-2, MOD)
for i in range(max_n, 0, -1):
    invfac[i-1] = invfac[i] * i % MOD

def comb(n, k):
    if k < 0 or k > n:
        return 0
    return fac[n] * invfac[k] % MOD * invfac[n-k] % MOD

A_seq = [0] * (2*s + 1)
for k in range(2*s + 1):
    c = comb(2*s, k)
    if k & 1:
        c = (MOD - c)
    A_seq[k] = c

rem = P - 2*s
B_seq = [comb(rem, l) for l in range(rem + 1)]

g_seq = [0] * (P + 1)
for k in range(2*s + 1):
    a = A_seq[k]
    if a:
        for l in range(rem + 1):
            g_seq[k+l] = (g_seq[k+l] + a * B_seq[l]) % MOD

powers = [0] * (P + 1)
for t in range(P + 1):
    d = P - 2*t
    base = (d*d - P) % MOD
    powers[t] = pow(base, m, MOD)

ans_num = 0
for t in range(P + 1):
    ans_num = (ans_num + g_seq[t] * powers[t]) % MOD

inv2 = (MOD+1)//2
inv_factor = pow(inv2, P + m, MOD)
ans = ans_num * inv_factor % MOD

print(ans)
0