結果
問題 | No.391 CODING WAR |
ユーザー | callitanything |
提出日時 | 2019-10-09 23:34:37 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 24 ms / 2,000 ms |
コード長 | 3,756 bytes |
コンパイル時間 | 1,653 ms |
コンパイル使用メモリ | 172,672 KB |
実行使用メモリ | 5,632 KB |
最終ジャッジ日時 | 2024-04-29 06:39:34 |
合計ジャッジ時間 | 2,757 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 6 ms
5,504 KB |
testcase_01 | AC | 6 ms
5,504 KB |
testcase_02 | AC | 6 ms
5,632 KB |
testcase_03 | AC | 6 ms
5,632 KB |
testcase_04 | AC | 6 ms
5,632 KB |
testcase_05 | AC | 6 ms
5,632 KB |
testcase_06 | AC | 5 ms
5,632 KB |
testcase_07 | AC | 6 ms
5,632 KB |
testcase_08 | AC | 6 ms
5,632 KB |
testcase_09 | AC | 24 ms
5,632 KB |
testcase_10 | AC | 23 ms
5,504 KB |
testcase_11 | AC | 6 ms
5,632 KB |
testcase_12 | AC | 6 ms
5,632 KB |
testcase_13 | AC | 20 ms
5,632 KB |
testcase_14 | AC | 19 ms
5,632 KB |
testcase_15 | AC | 20 ms
5,632 KB |
testcase_16 | AC | 15 ms
5,632 KB |
testcase_17 | AC | 17 ms
5,632 KB |
testcase_18 | AC | 13 ms
5,632 KB |
testcase_19 | AC | 13 ms
5,632 KB |
ソースコード
#include <bits/stdc++.h> using namespace std; struct Benri { Benri() { std::cin.tie(0); ios::sync_with_stdio(false); cout << fixed << setprecision(12);}} benri; using ll = long long; using vi = vector<int>; using vvi = vector<vi>; using pii = pair<int, int>; using vll = vector<long long>; using vvll = vector<vll>; using pll = pair<ll, ll>; using ull = unsigned long long; template <typename T> using PQ = priority_queue<T>; template <typename T> using minPQ = priority_queue<T, vector<T>, greater<T>>; #define rep(i, n) for (int i = 0; i < (int)(n); i++) #define all(x) (x).begin(),(x).end() #define pb push_back #define mp make_pair #define F first #define S second 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; } constexpr long long MOD = 1000000007; //constexpr long long MOD = 998244353; //constexpr int INF = 1001001001; constexpr ll INF = 1001001001001001001ll; constexpr double EPS = 1e-10; using number = long long; template< int64_t mod > struct mInt { int64_t x; mInt() : x(0LL) {} mInt(int64_t y) : x(y >= 0 ? y % mod : (mod - (-y) % mod) % mod) {} mInt &operator+=(const mInt &p) { if ((x += p.x) >= mod) x -= mod; return *this; } mInt &operator-=(const mInt &p) {if ((x += mod - p.x) >= mod) x -= mod; return *this;} mInt &operator*=(const mInt &p) { x = (x * p.x % mod); return *this;} mInt &operator/=(const mInt &p) { *this *= p.inverse(); return *this;} mInt operator-() const { return mInt(-x); } mInt operator+(const mInt &p) const { return mInt(*this) += p; } mInt operator-(const mInt &p) const { return mInt(*this) -= p; } mInt operator*(const mInt &p) const { return mInt(*this) *= p; } mInt operator/(const mInt &p) const { return mInt(*this) /= p; } bool operator==(const mInt &p) const { return x == p.x; } bool operator!=(const mInt &p) const { return x != p.x; } mInt inverse() const { int64_t 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 mInt(u); } mInt pow(int64_t n) const { mInt ret(1), mul(x); while (n > 0) {if (n & 1) ret *= mul; mul *= mul; n >>= 1;} return ret; } friend ostream &operator<<(ostream &os, const mInt &p) { return os << p.x; } friend istream &operator>>(istream &is, mInt &a) { int64_t t; is >> t; a = mInt< mod >(t); return (is); } static int64_t get_mod() { return mod; } }; using mint = mInt< MOD >; template<typename T, int FAC_MAX> struct Comb { vector<T> fac, ifac, iv; Comb() { fac.resize(FAC_MAX, 1); ifac.resize(FAC_MAX, 1); iv.resize(FAC_MAX, 1); for (int i = 2; i < FAC_MAX; i++) { fac[i] = fac[i - 1] * i; iv[i] = - iv[MOD % i] * T(MOD / i) ; ifac[i] = ifac[i - 1] * iv[i]; } } T aPb(int a, int b) { if (b < 0 || a < b) return T(0); return fac[a] * ifac[a - b]; } T aCb(int a, int b) { if (b < 0 || a < b) return T(0); return fac[a] * ifac[a - b] * ifac[b]; } T nHk(int n, int k) { if (n == 0 && k == 0) return T(1); if (n <= 0 || k < 0) return 0; return aCb(n + k - 1, k); } }; Comb<mint, 101010> com; mint stirling_number_second(long long n, int k) { mint ret = 0; for (int i = 0; i <= k; i++) { mint add = mint(i).pow(n) * com.aCb(k, i); if ((k - i) & 1) ret -= add; else ret += add; } return ret * com.ifac[k]; } int main() { ll N, M; cin >> N >> M; if (N < M) cout << 0 << endl; else cout << stirling_number_second(N, M) * com.fac[M] << endl; }