結果
問題 | No.391 CODING WAR |
ユーザー | en30 |
提出日時 | 2020-03-01 18:01:16 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 137 ms / 2,000 ms |
コード長 | 3,560 bytes |
コンパイル時間 | 1,427 ms |
コンパイル使用メモリ | 170,644 KB |
実行使用メモリ | 6,528 KB |
最終ジャッジ日時 | 2024-10-13 20:45:31 |
合計ジャッジ時間 | 3,288 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
5,248 KB |
testcase_01 | AC | 1 ms
5,248 KB |
testcase_02 | AC | 2 ms
5,248 KB |
testcase_03 | AC | 2 ms
5,248 KB |
testcase_04 | AC | 1 ms
5,248 KB |
testcase_05 | AC | 2 ms
5,248 KB |
testcase_06 | AC | 2 ms
5,248 KB |
testcase_07 | AC | 2 ms
5,248 KB |
testcase_08 | AC | 2 ms
5,248 KB |
testcase_09 | AC | 137 ms
6,528 KB |
testcase_10 | AC | 135 ms
6,528 KB |
testcase_11 | AC | 101 ms
6,400 KB |
testcase_12 | AC | 2 ms
5,248 KB |
testcase_13 | AC | 133 ms
6,528 KB |
testcase_14 | AC | 103 ms
5,760 KB |
testcase_15 | AC | 117 ms
6,016 KB |
testcase_16 | AC | 68 ms
5,248 KB |
testcase_17 | AC | 85 ms
5,248 KB |
testcase_18 | AC | 55 ms
5,248 KB |
testcase_19 | AC | 57 ms
5,248 KB |
ソースコード
#include <bits/stdc++.h> using namespace std; typedef long long ll; template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; } template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; } class ModInt { static int MOD; long long x; public: static void mod(int m) { MOD = m; } ModInt(long long v = 0) : x(v % MOD) { if (x < 0) x += MOD; } ModInt& operator+=(const ModInt& r) { x += r.x; if (x >= MOD) x -= MOD; return *this; } ModInt& operator-=(const ModInt& r) { x -= r.x; if (x < 0) x += MOD; return *this; } ModInt& operator*=(const ModInt& r) { x = (x * r.x) % MOD; return *this; } ModInt& operator/=(const ModInt& r) { *this *= r.inverse(); return *this; } ModInt operator-() const { return ModInt(-x); } ModInt operator+(const ModInt& r) const { return ModInt(*this) += r; } ModInt operator-(const ModInt& r) const { return ModInt(*this) -= r; } ModInt operator*(const ModInt& r) const { return ModInt(*this) *= r; } ModInt operator/(const ModInt& r) const { return ModInt(*this) /= r; } bool operator==(const ModInt& r) const { return x == r.x; } bool operator!=(const ModInt& r) const { return x != r.x; } ModInt inverse() const { long long a = x, b = MOD, 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(long long 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& x) { return os << x.x; } friend istream& operator>>(istream& is, ModInt& x) { return is >> x.x; } int getMod() { return MOD; } long long val() { return x; } }; int ModInt::MOD = 1000000007; template <typename T> class Combination { vector<T> fact, ifact; public: Combination(int nMax) : fact(nMax + 1), ifact(nMax + 1) { fact[0] = 1; for (int i = 0; i < nMax; ++i) fact[i + 1] = fact[i] * (i + 1); for (int i = 0; i < nMax + 1; ++i) ifact[i] = fact[i].inverse(); } T factorial(int n) const { return fact[n]; } T inverseFactorial(int n) const { return ifact[n]; } T P(int n, int k) const { if (n < 0 || k < 0 || n < k) return 0; return factorial(n) * inverseFactorial(n - k); } T C(int n, int k) const { if (n < 0 || k < 0 || n < k) return 0; return factorial(n) * inverseFactorial(n - k) * inverseFactorial(k); } T H(int n, int k) const { if (n < 0 || k < 0) return 0; return k == 0 ? 1 : C(n + k - 1, k); } }; class StirlingNumber { vector<vector<ModInt>> res; public: static ModInt calculate(long long N, int K) { Combination<ModInt> comb(K); ModInt res = 0; for (int i = 0; i <= K; ++i) { ModInt v = comb.C(K, i) * ModInt(i).pow(N); if ((K - i) % 2) res -= v; else res += v; } res *= comb.inverseFactorial(K); return res; } StirlingNumber(int N, int K) : res(N + 1, vector<ModInt>(K + 1, 0)) { res[0][0] = 1; for (int n = 1; n <= N; ++n) { for (int k = 1; k <= min(n, K); ++k) { res[n][k] = res[n - 1][k - 1] + res[n - 1][k] * k; } } } const vector<ModInt>& operator[](int n) const { return res[n]; } }; int main() { ll N; int M; cin >> N >> M; Combination<ModInt> comb(M); cout << comb.factorial(M) * StirlingNumber::calculate(N, M) << endl; return 0; }