perogram

【C++】nCr 組み合わせ数の実装

参考

f:id:peroon:20190402202040j:plain

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を取っていい代わりに高速に求める