組合せの計算方法まとめ

この間捻られたのでコンビネーションが回聞かれた場合の計算方法のまとめ

を事前計算

なので、階乗を事前計算しておけばで出る。 だいたいこれでいい。

template<typename T>
void Factorical(ll siz, vector<T>& out) {
  out.resize(siz + 1);
  out[0] = T(1);
  for (ll i = 0; i < siz; i++) {
    out[i + 1] = out[i] * (i + 1);
  }
}

template<typename T>
T Combi(ll a, ll b, vector<T>& fact) {
  if (a < 0 || b < 0 || a < b)
    return 0;
  return fact[a] / (fact[b] * fact[a - b]);
}

愚直に計算

がやたら大きくてがやたら小さいなら愚直に計算すればで求まる。

atcoder.jp

  mint2 ans = 1;  
  REP(j, m) {
      ans *= a[i] - j;
      ans /= j + 1;
  }

パスカルの三角形

Modの計算に素数以外が入ってくるなどで割り算が使えない時はパスカルの三角形で事前計算できる。

atcoder.jp

  REP(i, n) {
    c[i][0] = 1;    
    FOR(j, 1, i+1)
      c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % m;
  }

他にも捻ってる場合があったら教えてください。冪級数展開とか使えないかなぁ（うかばない）