src/Combination.hpp

• View this file on GitHub
• Last update: 2021-02-04 23:16:22+09:00
• Include: #include "src/Combination.hpp"

Depends on

• src/Modint.hpp

Verified with

• test/yukicoder/1081.test.cpp

Code

#pragma once

#include <vector>
#include <iostream>

#include "Modint.hpp"

template<class T = mint>
class Combination {
public:
    explicit Combination(int N = 110000) : fac(N + 1), inv(N + 1), finv(N + 1) { build(N + 1); }

    T operator()(int n, int k) {
        if (n < k || k < 0) return 0LL;
        return fac[n] * (finv[k] * finv[n - k]);
    }

private:
    void build(int N) {
        fac[0] = fac[1] = 1;
        inv[1] = 1;
        finv[0] = finv[1] = 1;

        for (int i = 2; i < N; i++) {
            fac[i] = fac[i - 1] * i;
            inv[i] = -inv[MOD % i] * (MOD / i);
            finv[i] = finv[i - 1] * inv[i];
        }
    }

    vector<T> fac, inv, finv;
};

#line 2 "src/Combination.hpp"

#include <vector>
#include <iostream>

#line 2 "src/Modint.hpp"

#include <cassert>
#line 5 "src/Modint.hpp"
#include <numeric>

using namespace std;
using lint = long long;

template<const int &Modulo>
struct Mint {

    lint val;
    constexpr Mint(lint v = 0) noexcept: val(v % Modulo) { if (val < 0) val += Modulo; }

    constexpr Mint &operator+=(const Mint &r) noexcept {
        val += r.val;
        if (val >= Modulo) val -= Modulo;
        return *this;
    }
    constexpr Mint &operator-=(const Mint &r) noexcept {
        val -= r.val;
        if (val < 0) val += Modulo;
        return *this;
    }
    constexpr Mint &operator*=(const Mint &r) noexcept {
        val = val * r.val % Modulo;
        return *this;
    }
    constexpr Mint &operator/=(const Mint &r) noexcept {
        lint a{r.val}, b{Modulo}, u{1}, v{0};
        while (b) {
            lint t = a / b;
            a -= t * b;
            a ^= b, b ^= a, a ^= b;
            u -= t * v;
            u ^= v, v ^= u, u ^= v;
        }
        assert(a == 1);
        val = val * u % Modulo;
        if (val < 0) val += Modulo;
        return *this;
    }

    constexpr Mint operator+(const Mint &r) const noexcept { return Mint(*this) += r; }
    constexpr Mint operator-(const Mint &r) const noexcept { return Mint(*this) -= r; }
    constexpr Mint operator*(const Mint &r) const noexcept { return Mint(*this) *= r; }
    constexpr Mint operator/(const Mint &r) const noexcept { return Mint(*this) /= r; }

    constexpr Mint operator-() const noexcept { return Mint(-val); }

    constexpr bool operator==(const Mint &r) const noexcept { return val == r.val; }
    constexpr bool operator!=(const Mint &r) const noexcept { return !((*this) == r); }
    constexpr bool operator<(const Mint &r) const noexcept { return val < r.val; }

    constexpr friend ostream &operator<<(ostream &os, const Mint<Modulo> &x) noexcept { return os << x.val; }
    constexpr friend istream &operator>>(istream &is, Mint<Modulo> &x) noexcept {
        lint tmp{};
        is >> tmp;
        x = Mint(tmp);
        return is;
    }

    [[nodiscard]] constexpr Mint pow(lint n) const noexcept {
        Mint res{1}, tmp{*this};
        while (n > 0) {
            if (n & 1) res *= tmp;
            tmp *= tmp;
            n >>= 1;
        }
        return res;
    }
};

constexpr int MOD = 1000000007;
using mint = Mint<MOD>;

int RMOD;
using rmint = Mint<RMOD>;
#line 7 "src/Combination.hpp"

template<class T = mint>
class Combination {
public:
    explicit Combination(int N = 110000) : fac(N + 1), inv(N + 1), finv(N + 1) { build(N + 1); }

    T operator()(int n, int k) {
        if (n < k || k < 0) return 0LL;
        return fac[n] * (finv[k] * finv[n - k]);
    }

private:
    void build(int N) {
        fac[0] = fac[1] = 1;
        inv[1] = 1;
        finv[0] = finv[1] = 1;

        for (int i = 2; i < N; i++) {
            fac[i] = fac[i - 1] * i;
            inv[i] = -inv[MOD % i] * (MOD / i);
            finv[i] = finv[i - 1] * inv[i];
        }
    }

    vector<T> fac, inv, finv;
};

Back to top page