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(…

解法1： 考え方 回答例 解法2：二分探索 & ルジャンドルの定理 考え方 回答例 解法1：考え方Editorial - Denso Create Programming Contest 2022 Winter(AtCoder Beginner Contest 280)素因数分解：Pythonで蟻本2-6 - 数学的な問題を解くコツ - 競プロはじめ…