c++ - m を法とする大きな n と k の二項係数を求める

Question

次の制約で nCk mod m を計算したい:

n<=10^18

k<=10^5

m=10^9+7

私はこの記事を読みました：

大きな n & k の二項係数 (nCk) の計算

ただし、ここでは m の値は 1009 です。したがって、ルーカスの定理を使用すると、a,b<=1009 の場合の aCb の 1009*1009 の異なる値を計算するだけで済みます。

上記の制約でそれを行う方法。与えられた制約で O(m*k) 空間の複雑さの配列を作成することはできません。

ヘルプ！

Answer 1

という事実を利用するだけで

(n, k) = n! / k! / (n - k)! = n*(n-1)*...*(n-k+1)/[k*(k-1)*...*1]

したがって、実際には2*k=2*10^5因数だけがあります。数の逆数については、素数であるため、kfxmの提案を使用できます。