概略
Combinationに係る諸計算のライブラリ
目次
アルゴリズム
逆元
$$ {}_{n} \mathrm{C} _ {r} = \frac{n!}{r!(n-r)!} $$ なので分数のmodを求めたい気持ちになる．ここで逆元を使う．
整数 $a$ と 素数 $p$ について $$ p = \left\lfloor \frac{p}{a} \right\rfloor \times a + p\%a $$ mod $p$ とすると $$ 0 \equiv \left\lfloor \frac{p}{a} \right\rfloor \times a + p\%a $$ $$ p\%a \equiv - \left\lfloor \frac{p}{a} \right\rfloor \times a $$ $$ p\%a \times a^{-1} \equiv - \left\lfloor \frac{p}{a} \right\rfloor $$ $$ a^{-1} \equiv - \left\lfloor \frac{p}{a} \right\rfloor \times (p\%a)^{-1} $$
ここで $p\%a < a$ であるから，小さい方から漸化的に求められる．
なお，$0^{-1}$ の値は未定義なので，最終的な式において $p\%a \neq 0$ でなければならない．そのため $p$ は素数である．（正確には $p$ と $a$ が互いに素）
パスカルの三角形
$$ \begin{cases} {}_{n} \mathrm{C} _ {r} = {}_{n-1} \mathrm{C} _ {r-1} + {}_{n-1} \mathrm{C} _ {r} \\ {}_{n} \mathrm{C} _ {0} = {}_{n} \mathrm{C} _ {n} = 1 \end{cases} $$
より漸化的に求められる．
実装例
逆元
$n,r \leq 10^6 $ 程度を想定している．$p$ は素数．
- Combination$(p)$ := mod $p$ 下で階乗，逆元，逆元の階乗を求める．
- $O(n)$
- C$(n,r)$, P$(n,r)$, H$(n,r)$ := $ {}_{n} \mathrm{C} _ {r} , {}_{n} \mathrm{P} _ {r} , {}_{n} \mathrm{H} _ {r} $
- $O(1)$
パスカルの三角形
$n,r \leq 10^3 $ 程度を想定している．$p$ は素数でなくてもよい．
- CombinationOnPascal$(p)$ := mod $p$ 下で二項係数を計算する．
- $O(nr)$
- C$(n,r)$, P$(n,r)$, H$(n,r)$ := $ {}_{n} \mathrm{C} _ {r} , {}_{n} \mathrm{P} _ {r} , {}_{n} \mathrm{H} _ {r} $
- $O(1)$
verify
AOJ1501 Grid — AIZU ONLINE JUDGE
mod 1,000,000,007 だと思っていたら～、mod 100,000,007 でした～。
チクショー！！
No.117 組み合わせの数 — yukicoder
D - 多重ループ - AtCoder Beginner Contest 021 — AtCoder