No.435

No.434 の制限が厳しいバージョンである.

基本的なやり方は No.434 と変わらない.

まずは $f(x)$ を $9$ の余りをとる関数と考える. ただし, 余りが $0$ のときは $9$ と考える.

No.434 と同様に ${}_nC_r$ の計算は以下のように行う.

$${}_nC_r = \frac{N-r+1}{r} {}_nC_{r-1}$$

No.434 では $N-r+1$, $r$ を素因数分解して素因数の数を数えていたが, 今回はこれでは間に合わない.

ここで, ある2数 $a, b$ があるとき, $a/b \equiv c \pmod 9$ となる $c$ を求めることを考える. $9$ は素数ではないので, 逆元を計算する方法は使えない.

そこで, $a = 3^ix$, $b = 3^jy$ ($x, y$ は $3$ で割り切れない) とおくと, $y$ は $9$ と互いに素なので $\mod 9$ での逆元が存在し, この数を $y^{\prime}$ とすると,

$$\frac{a}{b} \equiv \frac{x}{y}3^{i-j} \equiv xy^{\prime} 3^{i-j} \pmod 9$$

となる.

このように $3$ の素因数だけ別立てで計算すれば, 逆元が使えるようになる.