ARC 117 C - Tricolor Pyramid の mod3 まわりについての個人的な補足
問題
公式解説
解説にある通り、青白赤を0,1,2に対応させることで各ブロックは二項係数を使って最下段のブロックのから（二項係数の計算量は無視して）O(N)で求めることができるという問題。
この問題には更に 二項係数の計算において mod 3を求める という副題があり、こちらについて学びになった点をメモとして残す。
乗法逆元についておさらい
法Mが与えられたとき、Xの乗法逆元が求められるための条件は、MとXが互いに素であることである。（この条件を、「Mが素数であればよい」と勘違いしないように注意する）
競プロでよくあるのは、法として素数である 109+7 や 998244353 が与えられて、計算に扱う値がそれ未満の自然数なので、法と扱う数が必ず互いに素となる、というパターンでこの場合は逆元求めて計算を行うことができる。
一方で、この問題では法が3で、扱う数が3と互いに素ではない可能性があるため逆元を求めて計算を行おうとすると計算結果が壊れる。
例として を考えると、以下の様に分母に3が出てくるために逆元を求めることができない。
mod 3の計算方法の解説に対する補足
まず前提として二項係数は以下の様に式変形ができる。
この時、右辺も当然整数となる。
が3の倍数になるための条件
解説には という関数を定義して、
の場合、明らかに3の倍数であると言っている。
この条件によって何故3の倍数と言えるかを補足する。
まず、 が整数であることから、
とすると、
であることがわかる。（
となるなら明らかに整数にならない）
ここで、ある数が3の倍数であるなら という形で表すことができるはずで、
をこのように表すことができるための条件が
つまり
である、と解説では言っているのである。（分子側の3の個数が多くないと全体で3の倍数に成り得ないということ）
また上記の説明は、この条件を満たすときに限り は3の倍数になるということも示唆している。
が3の倍数以外の場合について
上記から3の場合とならないなら となることが分かった。
これはつまり、 における分母と分子の3を相殺できること意味し、相殺後の分母は3と互いに素になっているため、mod 3における逆元を求めることができる。
よって の場合は、
から3で割れるだけ割ってできた整数の mod 3 を求め（解説ではこれを
という関数で定義している）、あとは乗法逆元を使って
を求めればよい。（解説ではここを場合分けして求めている）
提出コード
おまけ
問題の副題として、法が 109+7 や 998244353 ではなく、逆元を求めたい数と互いに素ではない可能性があるという問題
問題ネタバレ
行列累乗が本題の問題。 解説: https://pione.hatenablog.com/#ARC-050-C---LCM-111
