ルーカスの定理による巨大な組み合わせ数の剰余計算
整数 \(n, m\) と素数 \(p\) に対して、以下の関係が成り立つ：
\[ \binom{n}{m} \bmod p = \binom{n \bmod p}{m \bmod p} \cdot \binom{\lfloor n/p \rfloor}{\lfloor m/p \rfloor} \bmod p \]
この定理は、\(n\) や \(m\) が非常に大きく、通常の逆元計算（フェルマーの小定理など）が使えない場合に特に有効である。たとえば、\(m\) が \(p\) の倍数だと逆元が存在せず ...
8月19日 04:23 投稿