結果

問題 No.2874 Gunegune Tree
ユーザー tomeruntomerun
提出日時 2024-09-06 22:05:20
言語 Crystal
(1.11.2)
結果
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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,812 KB
testcase_01 AC 2 ms
6,812 KB
testcase_02 AC 1 ms
6,944 KB
testcase_03 AC 3 ms
6,944 KB
testcase_04 AC 5 ms
6,940 KB
testcase_05 AC 2 ms
6,940 KB
testcase_06 AC 1 ms
6,940 KB
testcase_07 AC 8 ms
6,944 KB
testcase_08 AC 5 ms
6,940 KB
testcase_09 AC 2 ms
6,944 KB
testcase_10 AC 7 ms
6,940 KB
testcase_11 AC 6 ms
6,940 KB
testcase_12 AC 3 ms
6,944 KB
testcase_13 AC 8 ms
6,944 KB
testcase_14 AC 7 ms
6,940 KB
testcase_15 AC 2 ms
6,940 KB
testcase_16 AC 9 ms
6,944 KB
testcase_17 AC 2 ms
6,940 KB
testcase_18 AC 3 ms
6,944 KB
testcase_19 AC 2 ms
6,944 KB
testcase_20 AC 2 ms
6,944 KB
testcase_21 AC 3 ms
6,940 KB
testcase_22 AC 4 ms
6,944 KB
testcase_23 AC 4 ms
6,944 KB
testcase_24 AC 4 ms
6,940 KB
testcase_25 AC 7 ms
6,940 KB
testcase_26 AC 5 ms
6,940 KB
testcase_27 AC 9 ms
6,940 KB
testcase_28 AC 3 ms
6,940 KB
testcase_29 AC 6 ms
6,940 KB
testcase_30 AC 5 ms
6,944 KB
testcase_31 AC 4 ms
6,944 KB
testcase_32 AC 9 ms
6,940 KB
権限があれば一括ダウンロードができます

ソースコード

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