This documentation is automatically generated by competitive-verifier/competitive-verifier
// 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());
}
}
Env | Name | Status | Elapsed | Memory |
---|---|---|---|---|
g++ | yuki.txt |
![]() |
55 ms | 27 MB |
clang++ | yuki.txt |
![]() |
57 ms | 27 MB |