解法1：メモ化再帰 考え方 回答例 解法1：メモ化再帰考え方$f(n)=$1から初めて最終的にピッタリ$n$になる確率． $n=1$：$f(1)=1$ $n\neq 1$：$\displaystyle f(n) = \frac{1}{6} \sum_{k} f(n/\!/k)$（$(n\% k =0$かつ$k \in \{1,2,\ldots,6\})$） $n\neq 1$…

解法1：DP 考え方 回答例 解法2：再帰 考え方 回答例 解法1：DP考え方 後退解析をする（先手の勝ち負けが確定している最終状態から，逆に考えていく）． modの逆数：modの逆数 - 競プロはじめました youtu.be 回答例dp[i][j][k] = 先手がiにいて, 後手がjに…

考え方 回答例 考え方 余りだけを管理する． $10^n$の計算は，先に計算しておくか，繰り返し二乗法（繰り返し二乗法 - 競プロはじめました）を使う． ※Python の剰余演算子%は，除数（割る方の数）と同じ符号の結果を返す．回答例 from collections import d…

mod素数の逆数 $10^{9} + 7, 998244353$は素数． 素数$p$に対し，$X/ Y \pmod p=$(X * pow(Y, p - 2, p)) % p 【背景】 $p$を素数，$a$を$p$の倍数でない整数とすると\begin{aligned} a^{p-1} \equiv 1 \pmod p \end{aligned}が成り立つ（フェルマーの小定理…

解法1：メモ化再帰 考え方 回答例 解法1：メモ化再帰考え方modの逆数（modの逆数 - 競プロはじめました）さえわかれば，再帰的に計算できる． 回答例 import sys sys.setrecursionlimit(10 ** 6) from functools import lru_cache N, P = map(int, input().s…

考え方 回答例 考え方dp[i][j][k] = i個目までみてj個和をとったときのk (mod D)の最大値．回答例dのループ範囲に注意． N, K, D = map(int, input().split()) A = list(map(int, input().split())) dp = [[[-1] * D for _ in range(K + 1)] for _ in range(…

考え方 回答例 考え方modの逆数（modの逆数 - 競プロはじめました）さえわかれば，普通のDP．回答例dはゴールまでの距離． nxt(次の位置) = move(今いる位置，出目) dp[i回目に][位置jにいる] 確率． N, M, K = map(int, input().split()) mod = 998244353 i…