test/Modint-Binomial.test.cpp

• View this file on GitHub
• Last update: 2025-07-04 15:57:54+09:00
• Problem: https://yukicoder.me/problems/no/117

Depends on

• Binomial.cpp
• modint.cpp

Code

// competitive-verifier: PROBLEM https://yukicoder.me/problems/no/117
#include "../Binomial.cpp"
#include "../modint.cpp"
int main() {
    Binomial<modint<1000000007>> bin(2000000);
    int t;
    scanf("%d", &t);
    while (t--) {
        char op;
        int n, k;
        scanf("\n%c(%d,%d)", &op, &n, &k);
        if (op == 'C') printf("%d\n", bin.C(n, k).val());
        if (op == 'P') printf("%d\n", bin.P(n, k).val());
        if (op == 'H') printf("%d\n", bin.H(n, k).val());
    }
}

#line 1 "test/Modint-Binomial.test.cpp"
// competitive-verifier: PROBLEM https://yukicoder.me/problems/no/117
#line 1 "Binomial.cpp"
#include <bits/stdc++.h>
using namespace std;
template <typename T>
struct Binomial {
    vector<T> inv, fact, factinv;
    Binomial(int n) {
        inv.resize(n + 1);
        fact.resize(n + 1);
        factinv.resize(n + 1);
        inv[0] = fact[0] = factinv[0] = 1;
        for (int i = 1; i <= n; i++) fact[i] = fact[i - 1] * i;
        factinv[n] = fact[n].inv();
        inv[n] = fact[n - 1] * factinv[n];
        for (int i = n - 1; i >= 1; i--) {
            factinv[i] = factinv[i + 1] * (i + 1);
            inv[i] = fact[i - 1] * factinv[i];
        }
    }
    T C(int n, int r) {
        if (n < 0 || n < r || r < 0) return 0;
        return fact[n] * factinv[n - r] * factinv[r];
    }
    T P(int n, int r) {
        if (n < 0 || n < r || r < 0) return 0;
        return fact[n] * factinv[n - r];
    }
    T H(int n, int r) {
        if (n == 0 && r == 0) return 1;
        if (n < 0 || r < 0) return 0;
        return r == 0 ? 1 : C(n + r - 1, r);
    }
};
#line 1 "modint.cpp"

#line 3 "modint.cpp"
using namespace std;
template <int modulo>
struct modint {
    int x;
    modint() : x(0) {}
    modint(int64_t y) : x(y >= 0 ? y % modulo : (modulo - (-y) % modulo) % modulo) {}
    modint &operator+=(const modint &p) {
        if ((x += p.x) >= modulo) x -= modulo;
        return *this;
    }
    modint &operator-=(const modint &p) {
        if ((x += modulo - p.x) >= modulo) x -= modulo;
        return *this;
    }
    modint &operator*=(const modint &p) {
        x = (int)(1LL * x * p.x % modulo);
        return *this;
    }
    modint &operator/=(const modint &p) {
        *this *= p.inv();
        return *this;
    }
    modint operator-() const { return modint(-x); }
    modint operator+(const modint &p) const { return modint(*this) += p; }
    modint operator-(const modint &p) const { return modint(*this) -= p; }
    modint operator*(const modint &p) const { return modint(*this) *= p; }
    modint operator/(const modint &p) const { return modint(*this) /= p; }
    bool operator==(const modint &p) const { return x == p.x; }
    bool operator!=(const modint &p) const { return x != p.x; }
    modint inv() const {
        int a = x, b = modulo, u = 1, v = 0, t;
        while (b > 0) {
            t = a / b;
            swap(a -= t * b, b);
            swap(u -= t * v, v);
        }
        return modint(u);
    }
    modint pow(int64_t n) const {
        modint ret(1), mul(x);
        while (n > 0) {
            if (n & 1) ret *= mul;
            mul *= mul;
            n >>= 1;
        }
        return ret;
    }
    friend ostream &operator<<(ostream &os, const modint &p) { return os << p.x; }
    friend istream &operator>>(istream &is, modint &a) {
        int64_t t;
        is >> t;
        a = modint<modulo>(t);
        return (is);
    }
    int val() const { return x; }
    static constexpr int mod() { return modulo; }
    static constexpr int half() { return (modulo + 1) >> 1; }
};
#line 4 "test/Modint-Binomial.test.cpp"
int main() {
    Binomial<modint<1000000007>> bin(2000000);
    int t;
    scanf("%d", &t);
    while (t--) {
        char op;
        int n, k;
        scanf("\n%c(%d,%d)", &op, &n, &k);
        if (op == 'C') printf("%d\n", bin.C(n, k).val());
        if (op == 'P') printf("%d\n", bin.P(n, k).val());
        if (op == 'H') printf("%d\n", bin.H(n, k).val());
    }
}

Test cases

Env	Name	Status	Elapsed	Memory
g++	yuki.txt	AC	55 ms	27 MB
clang++	yuki.txt	AC	57 ms	27 MB

Back to top page