結果
問題 | No.117 組み合わせの数 |
ユーザー |
![]() |
提出日時 | 2019-07-08 08:07:46 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 83 ms / 5,000 ms |
コード長 | 4,555 bytes |
コンパイル時間 | 580 ms |
コンパイル使用メモリ | 63,260 KB |
実行使用メモリ | 18,856 KB |
最終ジャッジ日時 | 2024-10-07 17:26:37 |
合計ジャッジ時間 | 1,349 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 1 |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:128:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 128 | scanf("%d\n", &T); | ~~~~~^~~~~~~~~~~~ main.cpp:131:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 131 | scanf("%c(%d,%d)\n", &c, &n, &k); | ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
ソースコード
#include <iostream>#include <vector>// @require ./modular_arithmetics.cc 👇👇template<typename T, T MOD>struct ModType {public:using Int = T;static constexpr Int mod = MOD;ModType(long long _v = 0) : v(set(_v)) {}ModType(const ModType &r) : v(set(r.v)) {}Int get_val() const { return v; }bool operator<(ModType r) const { return v < r.v; }bool operator>(ModType r) const { return v > r.v; }bool operator<=(ModType r) const { return v <= r.v; }bool operator>=(ModType r) const { return v >= r.v; }bool operator==(ModType r) const { return v == r.v; }bool operator!= (ModType r) const { return v != r.v; }ModType operator-() const { return ModInt(v ? mod - v : v); }ModType &operator=(const ModType &r) { if (this != &r) v = set(r.v); return *this; }ModType operator++(){ if (++v == mod) v = 0; return *this; }ModType operator--(){ v = (v == 0 ? mod - 1 : v - 1); return *this; }ModType &operator+=(ModType r) { (v += r.v) %= mod; return *this; }ModType &operator-=(ModType r) { (v -= r.v - mod) %= mod; return *this; }// ModType &operator*=(ModType r) { v = (__uint128_t(v) * r.v) % mod; return *this; }ModType &operator*=(ModType r) { v = 1ULL * v * r.v % mod; return *this; }ModType &operator/=(ModType r) { *this *= r.inv(); return *this; }ModType operator+(ModType r) const { return ModType(*this) += r; }ModType operator-(ModType r) const { return ModType(*this) -= r; }ModType operator*(ModType r) const { return ModType(*this) *= r; }ModType operator/(ModType r) const { return ModType(*this) /= r; }ModType inv() const {long long a = v, b = mod, u = 1, w = 0;while (b) {long long t = a / b;std::swap(a -= t * b, b);std::swap(u -= t * w, w);}return ModType(u);}ModType pow(Int e) {ModType a = *this, x(1);for ( ; 0 < e; e >>= 1) { if (e & 1) x *= a; a *= a; }return x;}inline ModType pow(ModType &e) { return pow(e.v); }friend std::ostream &operator<<(std::ostream &os, const ModType &r) { return os << r.v; }friend std::istream &operator>>(std::istream &is, ModType &r) {is >> r.v; r.set();return is;}static std::vector<ModType> Inverse(const Int n = mod - 1) {std::vector<ModType> inv(n + 1);inv[1].v = 1;for (Int a = 2; a <= n; ++a)inv[a] = inv[mod % a] * T(mod - mod / a);return inv;}private:Int v;inline static Int set(const Int x) { return x < 0 ? (x % mod) + mod : x % mod; }inline void set() { v = set(v); }};using ModInt = ModType<int, 1000000007>;// -------------8<------- start of library -------8<------------------------struct Combination {const ModInt::Int mod = ModInt::mod;ModInt::Int N = 0;std::vector<ModInt> fact, inv_f;// MultiChoose を使用する場合は N = 2 * _n とするexplicit Combination(int _n) : N(_n < mod ? _n : mod - 1), fact(N + 1), inv_f(N + 1) {set();}void set() {fact[0] = 1;for (int i = 1; i <= N; ++i) fact[i] = fact[i - 1] * i;inv_f[N] = fact[N].inv();for (int i = N; 1 <= i; --i) inv_f[i - 1] = inv_f[i] * i;}void resize(int _n) {N = (_n < mod ? _n : mod - 1);fact.resize(N + 1);inv_f.resize(N + 1);set();}ModInt factorial(const int n) const { return fact[n]; }ModInt invFactorial(const int n) const { return inv_f[n]; }ModInt permutation(const int n, const int k) const {if (k < 0 || n < k) return ModInt(0);else return fact[n] * inv_f[n - k];}ModInt choose(const int n, const int k) const {if (n < 0 || k < 0 || n < k) return ModInt(0);else return fact[n] * inv_f[k] * inv_f[n - k];}ModInt multiChoose(const int n, const int k) const {if (n < 0 || k < 0) return ModInt(0);else return k == 0 ? 1 : choose(n + k - 1, k);}};// -------------8<------- end of library ---------8-------------------------int main() {Combination cm(2 * 1e6);int T, n, k;char c;scanf("%d\n", &T);while (T--) {scanf("%c(%d,%d)\n", &c, &n, &k);if (c == 'C') printf("%d\n", cm.choose(n, k).get_val());else if (c == 'P') printf("%d\n", cm.permutation(n, k).get_val());else if (c == 'H') printf("%d\n", cm.multiChoose(n, k).get_val());}return 0;}