問題
既存投稿一覧ページへのリンク
独り言
AtCoder360のC/D/Eを考えていると、自信なくすわ。
C/Dなんて理解するのに苦労したのにdiffが非常に低いし、Eは問題分けわからないし。
まばらに問題見てきたけど、モジュラ逆数って初めて遭遇したんじゃないかな。
モジュラ逆数と拡張ユークリッドの互除法を理解するを読んで要約理解できました。
中学・高校で水色持っている人達って、このレベルの問題はサクサク解けるの？？
多分、私が学生時代に挑戦してても無理だったと思うけど、まぁ上位勢は本気で魔境だからペースを崩さないようにマイペースで進めますか。
解法手順1
-
必要な定数と変数を初期化する。
- MOD: 998244353（問題で指定された法）
- n, k: 入力値（ボールの数と操作回数）
- dp: 動的計画法のテーブル（各操作回数での期待値を格納）
-
逆元を計算する。
- inv_n: nの逆元（mod MOD）
- inv_2: 2の逆元（mod MOD）
-
確率計算に必要な値を事前に計算する。
- p: 黒いボールが動く確率
- q: 黒いボールが端に移動する確率
-
動的計画法で各操作回数での期待値を計算する。
- dp[i+1] = dp[i] * (1-p) + (1-dp[i]) * q
- これは、前の状態から黒いボールが動かない確率と、端に移動する確率を考慮している
-
最終的な期待値を計算する。
- 最後の操作後、黒いボールが動かなかった場合とランダムな位置に移動した場合を考慮
- ans = dp[k] + (1-dp[k]) * (n+1)/2
-
計算結果をMODで割った余りを出力する。
ACコード1
ac.py
import logging
def setup_logger(debug_mode):
logger = logging.getLogger(__name__)
if not logger.handlers: # ハンドラが存在しない場合のみ追加
logger.setLevel(logging.DEBUG if debug_mode else logging.INFO)
formatter = logging.Formatter('%(asctime)s - %(name)s - %(levelname)s - %(message)s')
file_handler = logging.FileHandler('program_trace.log', encoding="utf8")
file_handler.setFormatter(formatter)
logger.addHandler(file_handler)
return logger
# 法を定義
MOD = 998244353
def io_func():
# 標準入力からnとkを読み取る
return map(int, input().split())
def solve(n, k, logger):
logger.debug("動的計画法の計算を開始")
# dpテーブルを初期化
dp = [0] * (k + 1)
dp[0] = 1 # 初期状態では黒いボールは必ず左端にある
# nとnの逆元を計算
inv_n = pow(n, -1, MOD)
inv_2 = pow(2, -1, MOD)
# 確率pとqを計算
p = 2 * (n - 1) * inv_n * inv_n % MOD
q = 2 * inv_n * inv_n % MOD
logger.debug(f"確率計算: p = {p}, q = {q}")
# 動的計画法で期待値を計算
for i in range(k):
dp[i+1] = dp[i] * (1 + MOD - p) + (1 - dp[i] + MOD) * q
dp[i+1] %= MOD
logger.debug(f"ステップ {i+1}: dp[{i+1}] = {dp[i+1]}")
# 最終的な期待値を計算
ans = dp[k] + (1 - dp[k] + MOD) * inv_2 * (n + 2)
ans %= MOD
logger.debug(f"最終的な期待値: {ans}")
return ans
def main():
logger = setup_logger(debug_mode=False)
n, k = io_func()
result = solve(n, k, logger)
print(result)
if __name__ == "__main__":
main()
# ###
# - MOD: 計算結果を割る法（998244353）
# - n: ボールの総数
# - k: 操作回数
# - dp: 動的計画法のテーブル。各要素は各操作回数での黒いボールが左端にある確率
# - inv_n: nの逆元（mod MOD）
# - inv_2: 2の逆元（mod MOD）
# - p: 黒いボールが動く確率
# - q: 黒いボールが端に移動する確率
# - ans: 最終的な期待値
# 1. io_func関数: 標準入力からnとkを読み取る
# 2. solve関数: 主な計算ロジックを実装
# a. dpテーブルを初期化
# b. 逆元と確率を計算
# c. 動的計画法で各操作回数での期待値を計算
# d. 最終的な期待値を計算
# 3. main関数: プログラムのエントリーポイント
# a. ロガーをセットアップ
# b. 入力を受け取る
# c. solve関数を呼び出し
# d. 結果を出力