nがとても大きいときに、TLEせずにnCr mod pを求める（実装も載っているよ）
前のABCで出た問題で、$ nがとても大きいときに$ _n \mathrm{C} _r \ mod \ pを求める方法を使う問題が出たので、メモ程度に書いておきます。 どんな時にこの方法が使えるの？
$ n \leqq 10^9,r \leqq 10^7かつ、$ nが固定値のとき
いつもなら$ \displaystyle _n \mathrm{C} _r = \frac{n!}{r!(n - r)!} = n! \times (r!)^{-1} \times ((n - r)!)^{-1}を使って求めるが、これだと計算量が$ O(n)になってしまう、$ n \leqq 10^9のときにTLEしてしまう。そこで、少し見方を変えて、計算量をもっと落とすことを考える。
手計算で$ _n \mathrm{C} _rを求めるときは、上の公式を使わずに、
$ \displaystyle \frac{n \times (n - 1) \times \cdots \times (n - r + 1)}{1 \times 2 \times \cdots \times r}
を使って求めると思う。（例：$ _6 \mathrm{C} _3を求めるときは、$ \frac{6 \times 5 \times 4}{1 \times 2 \times 3} = 20というように求める）
これをそのまま実装してみる。
まず、$ _n \mathrm{C} _0 = 1である。すると、
$ \displaystyle _n \mathrm{C} _1 = \ _n \mathrm{C} _0 \times \frac{n}{1}
$ \displaystyle _n \mathrm{C} _2 = \ _n \mathrm{C} _1 \times \frac{n - 1}{2}
$ \vdots
$ \displaystyle _n \mathrm{C} _r = \ _n \mathrm{C} _{r - 1} \times \frac{n - r + 1}{r} \ (1 \leqq r \leqq n)
となることが分かる。
よって、動的計画法みたいな感じで$ _n \mathrm{C} _rが$ O(r)で求まることが分かる。
ここで気を付けたいのは、割り算をするときに、そのまま割ってしまうと、誤差が生じてしまう恐れがある。そこで、逆元を使って、誤差なく$ _n \mathrm{C} _rを求める。逆元を求める際に、$ O(\log p)かかるので、これを$ r回繰り返すから、最終的な計算量は$ O(r \log p)になる。
code:nCr.cpp
using namespace std;
typedef long long ll;
const ll MOD = 1000000007;
ll N;
//a^n mod MODを求める関数で、繰り返し二乗法を使っている
ll modpow(ll a,ll n) {
ll res = 1;
while (n > 0) {
if (n & 1) {
res = res * a % MOD;
}
a = a * a % MOD;
n >>= 1;
}
return res;
}
//逆元(= a ^ (p - 2))を求める
ll modinv(ll a) {
return modpow(a,MOD - 2);
}
void COM(int n) {
for(int i = 1;i < 10000010;i++) {
comi = comi - 1 * (n - (i - 1)) % MOD * modinv(i) % MOD; }
return;
}