脳log[20230327]

2023年03月27日 (月) [AtCoder] 精進。ABC228-E「Integer Sequence Fair」(水 diff)。以前に WA を出している>提出 #36786504 (WA×15)。今日改めて取り組んでみて書いたものが図らずもその WA 解答と一字一句同じだった(違ったのは空行が１つあるかないかだけ)。まるで成長していない……。■提出 #40106188 (AC / 92 Byte / 66 ms)。テストケースを利用しました。どうやら良くなかったのは mod を取った累乗を指数にしてまた累乗を計算したことらしい(mod を取らずに指数にする累乗を計算したら AC と解答不能に分かれたので)。足し算引き算掛け算は mod 付きでも自由にできるけど、割り算はちょっと制限があって、そして累乗もそのままではできないらしい。がちゃがちゃデバッグをやりました。逆元の計算でおなじみフェルマーの小定理があるじゃないですか。勘違いして最初は P-2 を mod にしたのだけど、P-1 にすると具合がいいようだった。だけどときどき間違える。そういうのはだいたい全か無か、P か P-1 か 0 かという違いですよ(「悲しさを考える前にまず m で割った n 個の余りについて考える。(中略)。余りが 0 の項の悲しさが 0 であることに注意して……」)。というわけで 0 に目を付けて P-1 に補正したらうまくいきましたね。こんなんで AC をとっても身にならないね！■「勘違いして最初は P-2 を mod にしたのだけど、P-1 にすると具合がいいようだった。」 勘違いしていたというのが勘違いだったみたいで、モジュラ逆数を計算するなら P-2 乗で間違いない。P-2、P-1、P 乗がそれぞれ 1/A、1、A に対応する雰囲気。