参考
- http://www.nct9.ne.jp/m_hiroi/linux/cpp08.html#ans06
- 順列で書くと桁あふれする
- nCr, nCr-1の関係式から再帰で求められる
- 追記：競プロではこれを使うことはほぼなく、逆元を使う
long long combination(int n, int r) { if (n == r || r == 0) return 1; else return combination(n, r - 1) * (n - r + 1) / r; }
注意点🤔
- n = 100000など大きいときは遅い
- n = 500000などで再帰が深すぎてSegmentation Faultになる
- メモ化するにしても2次元配列になるので必要メモリ数が多すぎる
- 競プロサイトのメモリ制限 (1GB) などを越える
- int a[100000][100000] = 4byte * 1010 = 40GB
TLEになる例 (n=100000)🤔
https://atcoder.jp/contests/abc066/submissions/3919189
modを取っていい代わりに高速に求める
verify
- D - aab aba baa (N<=60)
