結果

問題 No.2874 Gunegune Tree
コンテスト
ユーザー tomerun
提出日時 2024-09-06 22:05:20
言語 Crystal
(1.14.0)
結果
AC  
実行時間 9 ms / 2,000 ms
コード長 991 bytes
コンパイル時間 13,677 ms
コンパイル使用メモリ 296,120 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-09-06 22:05:51
合計ジャッジ時間 12,488 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

diff # 

MOD = 998244353i64

def inv(v : Int64)
  pow(v, MOD - 2)
end

def pow(v : Int64, p)
  ret = 1i64
  while p > 0
    if (p & 1i64) != 0
      ret *= v
      ret %= MOD
    end
    v *= v
    v %= MOD
    p >>= 1
  end
  ret
end

n = read_line.to_i64
inv5 = inv(5i64)
inv3 = inv(3i64)
inv2 = inv(2i64)
dp0 = [0i64, inv5 * 2, inv5] # 横、斜め、縦
dp1 = Array.new(3, 0i64)
prob0 = [inv5 * 2, inv5 * 2, inv5]
prob1 = Array.new(3, 0i64)
(n - 1).times do
  dp1.fill(0i64)
  prob1.fill(0i64)
  dp1[0] = dp0[0] * inv2 + dp0[1] * inv3
  dp1[1] = (dp0[0] + prob0[0]) * inv2 + (dp0[1] + prob0[1]) * inv3 + (dp0[2] + prob0[2]) * inv3 * 2
  dp1[2] = (dp0[1] + prob0[1]) * inv3 + (dp0[2] + prob0[2]) * inv3
  prob1[0] = prob0[0] * inv2 + prob0[1] * inv3
  prob1[1] = prob0[0] * inv2 + prob0[1] * inv3 + prob0[2] * inv3 * 2
  prob1[2] = prob0[1] * inv3 + prob0[2] * inv3
  dp1.map! { |v| v % MOD }
  prob1.map! { |v| v % MOD }
  dp0, dp1 = dp1, dp0
  prob0, prob1 = prob1, prob0
end
puts dp0.sum % MOD
0