n!, nPr, nCr, nHr 構造体

概要

mod素数での組み合わせを求めるのに使う構造体．

使い方

comb cm(): 階乗とその逆数を前計算する．デフォルトで mod は 1000000007, 引数の上限は 3000000．
cm.fact(n): $n!$
cm.inv_fact(n): $(n!)^{-1}$
cm.inv(n): $n^{-1}$
cm.pow(n, a): $n^a$
cm.perm(n, r): $n \times (n-1) \times \dots \times (n-r+1)$
cm.binom(n, r): $\binom{n}{r} = n \times (n-1) \times \ldots \times (n-r+1) / r / (r-1) / \dots / 1$
cm.homo(n, r): $\binom{n + r - 1}{r}$

実装

template <typename Int, Int MOD, int N>
struct comb_util {
    std::array<Int, N + 1> fc, ifc;

    comb_util() {
        fc[0] = 1;
        for (int i = 1; i <= N; i++) fc[i] = fc[i - 1] * i % MOD;
        ifc[N] = inv(fc[N]);
        for (int i = N - 1; i >= 0; i--) ifc[i] = ifc[i + 1] * (i + 1) % MOD;
    }

    Int fact(Int n) { return fc[n]; }

    Int inv_fact(Int n) { return ifc[n]; }

    Int inv(Int n) { return pow(n, MOD - 2); }

    Int pow(Int n, Int a) {
        Int res = 1, exp = n;
        for (; a; a /= 2) {
            if (a & 1) res = res * exp % MOD;
            exp = exp * exp % MOD;
        }
        return res;
    }

    Int perm(Int n, Int r) {
        if (r < 0 || n < r)
            return 0;
        else
            return fc[n] * ifc[n - r] % MOD;
    }

    Int binom(Int n, Int r) {
        if (n < 0 || r < 0 || n < r) return 0;
        return fc[n] * ifc[r] % MOD * ifc[n - r] % MOD;
    }

    Int homo(Int n, Int r) {
        if (n < 0 || r < 0) return 0;
        return r == 0 ? 1 : binom(n + r - 1, r);
    }
};

using comb = comb_util<long long, 1000000007, 3000000>;

検証

yukicoder No.117 http://yukicoder.me/submissions/145951