競プロ用の組み合わせ前計算テンプレート（階乗、順列、組み合わせ、重複組合せ）

二項係数nCr、1<=r<=n の範囲を事前計算してテーブル作れば、前計算O(n)、以後O(1)だし割と困らない？？

— なかしー (@nakashiii2020) 2022年5月23日

ということで、以下の4つをO(n)で前計算して、O(1)で呼び出せるようにする

• 階乗
• 順列 nPr
• 組み合わせ nCr
• 重複組み合わせ nHr

実装

ちょっと補足

• DPとかで使えるように AtCoderライブラリのModint を使っている
• 変数はグローバルに宣言してあって、mainで対象の関数を呼び出して初期化する
• 【注意】きちんと動作確認していないので、バグっていたらごめんなさい

// modを問題文にあわせること！！！忘れずに！！！！！！
using mint = modint1000000007;

vector<mint> fact;  // rの階乗
vector<mint> nPr;   // n個から r個取り出す 順列
vector<mint> nCr;   // n個から r個取り出す 組み合わせ
vector<mint> nHr;   // n個から r個取り出す 重複組み合わせ

void pre_calc(ll n) {
  // 初期化
  fact.assign(n + 10, 1);
  nPr.assign(n + 10, 1);
  nCr.assign(n + 10, 1);
  nHr.assign(n + 10, 1);

  // 組み合わせ用
  for (ll r = 1; r <= n; r++) {
    fact[r] = fact[r - 1] * r;
    nPr[r] = nPr[r - 1] * (n + 1 - r);
    nCr[r] = nPr[r] / fact[r];
  }

  // 重複組合せ用
  mint top = 1;     // 分子
  mint bottom = 1;  // 分母
  for (ll r = 1; r <= n; r++) {
    top *= (n + r - 1);
    bottom *= r;
    nHr[r] = top / bottom;
  }
}

// これをmainで呼ぶ. nは取り出す母数
// pre_calc(n);

おまけ

この問題を解いている時に欲しくなった。 E - Roaming

もし上記の実装間違っていたら、Twitter、もしくはブログコメントで教えて頂けるとうれしいですm(_ _)m