結果
問題 | No.117 組み合わせの数 |
ユーザー |
![]() |
提出日時 | 2015-08-20 15:04:46 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 310 ms / 5,000 ms |
コード長 | 5,368 bytes |
コンパイル時間 | 1,387 ms |
コンパイル使用メモリ | 164,184 KB |
実行使用メモリ | 26,476 KB |
最終ジャッジ日時 | 2024-07-18 10:53:17 |
合計ジャッジ時間 | 2,369 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 1 |
ソースコード
#include <bits/stdc++.h>using namespace std;template<typename T> inline T gcd(T a, T b) {return __gcd(a, b);}template<typename T> inline T lcm(T a, T b) {return a / gcd(a, b) * b;}template<typename T> inline T floor(T a, T b) {return floor(a / b) * b <= a ? floor(a / b) : floor(a / b) - 1;}template<typename T> inline T ceil(T a, T b) {return floor(a + b - 1, b);}template<typename T> inline T round(T a, T b) {return floor(a + b / 2);}template<typename T> inline T mod(T a, T b) {return a - floor(a, b) * b;}template<typename T> inline T factorial(T n) {return n <= 1 ? 1 : factorial(n - 1) * n;}template<typename T> inline T square(T n) {return n * n;}template<typename T> inline T cube(T n) {return n * n * n;}template<typename T> inline T norm(T x1, T y1, T x2, T y2) {return square(x1 - x2) + square(y1 - y2);}inline long long sqrt(long long n) {return sqrt((long double)n);}template<typename T> class Combination {private:vector<T> factorial;public:Combination(int n = 0) : factorial(n + 1, 1) {for (int i = 1; i <= n; ++i) factorial[i] = factorial[i - 1] * i;}T partial_permutation(int n, int m) {if (n < m) return 0;if (n < (int)factorial.size()) return factorial[n] / factorial[n - m];T res = 1;for (int i = n; i > n - m; --i) res *= i;return res;}T combination(int n, int m) {if (n < m) return 0;if (n < (int)factorial.size()) return factorial[n] / factorial[m] / factorial[n - m];T res = 1;for (int i = 0; i < min(m, n - m); ++i) res = res * (n - i) / (i + 1);return res;}T combination_safety(int n, int m) {m = min(m, n - m);vector<int> a(m), b(m);iota(a.begin(), a.end(), n - m + 1);iota(b.begin(), b.end(), 1);for (auto i : b) {for (auto& j : a) {auto g = gcd(i, j);i /= g;j /= g;if (i == 1) break;}}return accumulate(a.begin(), a.end(), T(1), multiplies<T>());}T repetition(int n, int m) {if (m == 0) return 1;return combination(n + m - 1, m);}};namespace arithmetic {template<typename T> class Addition {public:template<typename V> T operator+(const V& v) const {return T(static_cast<const T&>(*this)) += v;}};template<typename T> class Subtraction {public:template<typename V> T operator-(const V& v) const {return T(static_cast<const T&>(*this)) -= v;}};template<typename T> class Multiplication {public:template<typename V> T operator*(const V& v) const {return T(static_cast<const T&>(*this)) *= v;}};template<typename T> class Division {public:template<typename V> T operator/(const V& v) const {return T(static_cast<const T&>(*this)) /= v;}};template<typename T> class Modulus {public:template<typename V> T operator%(const V& v) const {return T(static_cast<const T&>(*this)) %= v;}};}template<typename T> class IndivisibleArithmetic : public arithmetic::Addition<T>, public arithmetic::Subtraction<T>, public arithmetic::Multiplication<T> {};template<typename T> class Arithmetic : public IndivisibleArithmetic<T>, public arithmetic::Division<T> {};class Inverse {private:long long mod;vector<long long> inv;public:Inverse() {}Inverse(long long mod, long long n = 1000000) : mod(mod) {inv = vector<long long>(n, 1);for (int i = 2; i < n; ++i) inv[i] = inv[mod % i] * (mod - mod / i) % mod;}long long operator()(long long a) const {if (a < (int)inv.size()) return inv[a];long long b = mod, x = 1, y = 0;while (b) {long long t = a / b;swap(a -= t * b, b);swap(x -= t * y, y);}return (x %= mod) < 0 ? x + mod : x;}};class Mint : public Arithmetic<Mint> {private:static long long mod;static Inverse inverse;long long val;public:Mint() : val(0) {}Mint(const long long& val) {this->val = val % mod;if (this->val < 0) this->val += mod;}static void setMod(const long long& m) {mod = m;inverse = Inverse(m);}Mint operator+=(const Mint& m) {val += m.val;if (val >= mod) val -= mod;return *this;}Mint operator-=(const Mint& m) {val -= m.val;if (val < 0) val += mod;return *this;}Mint operator*=(const Mint& m) {val *= m.val;val %= mod;return *this;}Mint operator/=(const Mint& m) {val *= inverse(m.val);val %= mod;return *this;}Mint operator++() {return val += 1;}Mint operator--() {return val -= 1;}operator long long() {return val;}Mint identity() const {return 1;}};long long Mint::mod = 1000000007;Inverse Mint::inverse(1000000007);ostream& operator<<(ostream& os, Mint a) {os << (long long)a;return os;}istream& operator>>(istream& is, Mint& a) {long long n;is >> n;a = n;return is;}int main() {Combination<Mint> comb(2000000);int t;cin >> t;for (int i = 0; i < t; ++i) {char c;int n, k;cin >> c;cin.ignore();cin >> n;cin.ignore();cin >> k;cin.ignore();switch (c) {case 'C': cout << comb.combination(n, k) << endl; break;case 'P': cout << comb.partial_permutation(n, k) << endl; break;case 'H': cout << comb.repetition(n, k) << endl; break;}}}