前計算した階乗による nCr

多くの問題では、n 個の項目から r 個を選ぶ方法の数を nCr として求めます。コンテストでは、この個数を素数を法として求めることがよくあります。🧮

基本的な公式は、nCr が n の階乗を、r の階乗と n−r の階乗の積で割ったものだということです。問題は、mod の下では割り算ができないことです。

1つの階乗だけでも非常に大きくなるため、それぞれを p で割った余りにします。これにより各値を小さく保ちながら、modulus の下では公式を正確に維持できます。

必要な最大の n まで、fact 配列を一度だけ作成します。各要素は1つ前の要素に添字を掛け、計算のたびに p で割った余りを取ります。

公式では2つの階乗で割るため、それらの法逆元が必要です。逆元を使えば、割り算を簡単な乗算に変えられることを思い出してください。

最大の階乗の逆元を、フェルマーの小定理を使って一度だけ求めます。指数 p−2 で pow を呼び出し、その結果を残りの計算の基準にします。

残りの逆階乗は、次の要素に添字を掛ける形で、後ろ向きに1回走査して求めます。追加の pow 呼び出しは必要ありません。

これで nCr は、fact[n] と inv_fact[r] と inv_fact[n−r] を掛け合わせ、すべてを p で割った余りを取るだけです。クエリごとに3回の参照と2回の乗算で済みます。

前計算の後は、組み合わせの各クエリを O(1) で答えられます。そのため、nCr の値を何千個も求める問題でこの方法が力を発揮します。

r が負、または n より大きい場合、答えは 0 です。階乗配列の範囲外を参照しないよう、まずこの条件を確認してください。

すべてのクエリにおける最大の n に少し余裕を加えたサイズで配列を作ります。小さすぎるlimitは、ここでよくあるインデックスエラーの原因です。

前計算の後、1回の nCr クエリはどれくらいの速さで処理できますか。

これで、階乗とその逆元を一度だけ前計算し、3回の参照によって各 nCr を O(1) で求められるようになりました。r の範囲を確認し、十分大きな配列を用意しましょう。🏆