私は何度もこの問題に遭遇しましたが、それを解決することはできません。答えが間違っている場合や、私が書いたプログラムが遅すぎる場合があります。正式に私は計算について話している
nCk mod pここで、pは素数であり、nは大きな数であり、1 <= k<=nです。
私は何を試しましたか：
階乗の再帰的定式化とそれを動的計画問題としてモデル化することは知っていますが、それは遅いと感じています。再帰的な定式化は(nCk) + (nCk-1) = (n+1Ck)です。オーバーフローを回避するために配列に値を格納するときにモジュラスを処理しmod pましたが、結果に対してを実行するだけで、削除する必要がある可能性があるため、すべてのオーバーフローを回避できるかどうかはわかりません。
まず、p が比較的小さい場合を考えてみましょう。n と k の基数 p 展開を取ります: n = n_0 + n_1 p + n_2 p^2 + ... + n_m p^m および k = k_0 + k_1 p + ... + k_m p^m と記述します。 n_i で、各 k_i は 0 以上 p 未満です。定理 (これは Edouard Lucas によるものだと思います) は、C(n,k) = C(n_0, k_0) * C(n_1, k_1) * ... * C(n_m, k_m) と述べています。これは、以下の「n が比較的小さい」場合の数値の mod-p 積を取ることになります。
次に、n が比較的小さい場合、式 C(n,k) = C(n-1,k-1) + C(n-1,k) で動的計画法を使用して二項係数を計算し、mod p を減らすことができます。各ステップで。または、もっと賢いことをしてください。
第 3 に、k が比較的小さい (そして p より小さい) 場合、n!/(nk)! を計算することにより、n!/(k!(nk)!) mod p を計算できるはずです。n * (n-1) * ... * (n-k+1) として、各積の後にモジュロ p を減らし、1 と k の間の各数値のモジュロ逆数を掛けます。
「配列に値を格納する」とはどういう意味かわかりませんが、冗長な計算を避けて処理を高速化するために、実行中に配列がルックアップテーブルとして機能すると思います。これにより、速度の問題が処理されます。オーバーフローについては、計算のどの段階でもモジュロ演算を実行し、必要なだけ繰り返すことができます。結果は正しくなります。