結果
問題 | No.391 CODING WAR |
ユーザー | AC2K |
提出日時 | 2023-05-05 00:08:24 |
言語 | C++23 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 49 ms / 2,000 ms |
コード長 | 9,749 bytes |
コンパイル時間 | 5,996 ms |
コンパイル使用メモリ | 307,424 KB |
実行使用メモリ | 22,784 KB |
最終ジャッジ日時 | 2024-05-02 03:13:19 |
合計ジャッジ時間 | 7,023 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 17 ms
22,656 KB |
testcase_01 | AC | 16 ms
22,620 KB |
testcase_02 | AC | 16 ms
22,548 KB |
testcase_03 | AC | 16 ms
22,656 KB |
testcase_04 | AC | 16 ms
22,688 KB |
testcase_05 | AC | 4 ms
7,040 KB |
testcase_06 | AC | 16 ms
22,656 KB |
testcase_07 | AC | 17 ms
22,784 KB |
testcase_08 | AC | 16 ms
22,596 KB |
testcase_09 | AC | 49 ms
22,656 KB |
testcase_10 | AC | 46 ms
22,636 KB |
testcase_11 | AC | 4 ms
7,168 KB |
testcase_12 | AC | 16 ms
22,528 KB |
testcase_13 | AC | 44 ms
22,708 KB |
testcase_14 | AC | 40 ms
22,560 KB |
testcase_15 | AC | 43 ms
22,552 KB |
testcase_16 | AC | 31 ms
22,528 KB |
testcase_17 | AC | 34 ms
22,656 KB |
testcase_18 | AC | 29 ms
22,636 KB |
testcase_19 | AC | 29 ms
22,656 KB |
ソースコード
#line 1 "main.cpp" #include <atcoder/all> #line 2 "library/src/math/static_modint.hpp" #include <cassert> #include <iostream> #line 3 "library/src/math/gcd.hpp" #include <tuple> namespace kyopro { template <typename T> constexpr T inline _gcd(T a, T b) { assert(a >= 0 && b >= 0); if (a == 0 || b == 0) return a + b; int d = std::min<T>(__builtin_ctzll(a), __builtin_ctzll(b)); a >>= __builtin_ctzll(a), b >>= __builtin_ctzll(b); while (a != b) { if (!a||!b) { return a + b; } if (a >= b) { a -= b; a >>= __builtin_ctzll(a); } else { b -= a; b >>= __builtin_ctzll(b); } } return a << d; } template <typename T> constexpr T ext_gcd(T a, T b, T& x, T& y) { x = 1, y = 0; T nx = 0, ny = 1; while (b) { T q = a / b; std::tie(a, b) = std::pair<T, T>{b, a % b}; std::tie(x, nx) = std::pair<T, T>{nx, x - nx * q}; std::tie(y, ny) = std::pair<T, T>{ny, y - ny * q}; } return a; } }; // namespace kyopro #line 5 "library/src/math/static_modint.hpp" namespace kyopro { template <__uint64_t mod> class static_modint { private: using mint = static_modint<mod>; using i64 = long long; using u64 = unsigned long long; using u128 = __uint128_t; using i128 = __int128_t; u64 v; constexpr inline u64 normalize(i64 v_) const { v_ %= mod; if (v_ < 0) { v_ += mod; } return v_; } public: constexpr static_modint() : v(0) {} constexpr static_modint(i64 v_) : v(normalize(v_)) {} // operator constexpr u64 val() const { return v; } constexpr mint& operator+=(const mint& rhs) { v += rhs.val(); if (v >= mod) { v -= mod; } return (*this); } constexpr mint& operator-=(const mint& rhs) { v += mod - rhs.val(); if (v >= mod) { v -= mod; } return (*this); } constexpr mint& operator*=(const mint& rhs) { v = (u128)v * rhs.val() % mod; return (*this); } constexpr mint operator+(const mint& r) const { return mint(*this) += r; } constexpr mint operator-(const mint& r) const { return mint(*this) -= r; } constexpr mint operator*(const mint& r) const { return mint(*this) *= r; } constexpr mint& operator+=(const i64& rhs) { (*this) += mint(rhs); return (*this); } constexpr mint& operator-=(const i64& rhs) { (*this) -= mint(rhs); return (*this); } constexpr mint& operator*=(const i64& rhs) { (*this) *= mint(rhs); return (*this); } constexpr friend mint operator+(const i64& l, const mint& r) { return mint(l) += r; } constexpr friend mint operator-(const i64& l, const mint& r) { return mint(l) -= r; } constexpr friend mint operator*(const i64& l, const mint& r) { return mint(l) *= r; } constexpr mint operator+(i64 r) { return mint(*this) += r; } constexpr mint operator-(i64 r) { return mint(*this) -= r; } constexpr mint operator*(i64 r) { return mint(*this) *= r; } constexpr mint& operator=(i64 r) { return (*this) = mint(r); } constexpr bool operator==(const mint& r) const { return (*this).val() == r.val(); } template <typename T> constexpr mint pow(T e) const { mint ans(1), base(*this); while (e) { if (e & 1) { ans *= base; } base *= base; e >>= 1; } return ans; } constexpr inline mint inv() const { long long x, y; auto d = ext_gcd((long long)mod, (long long)v, x, y); assert(d == 1); return mint(y); } constexpr mint& operator/=(const mint& r) { return (*this) *= r.inv(); } constexpr mint inv(const mint& r) const { return mint(*this) *= r.inv(); } constexpr friend mint operator/(const mint& l, i64 r) { return mint(l) /= mint(r); } constexpr friend mint operator/(i64 l, const mint& r) { return mint(l) /= mint(r); } // iostream constexpr friend std::ostream& operator<<(std::ostream& os, const mint& mt) { os << mt.val(); return os; } constexpr friend std::istream& operator>>(std::istream& is, mint& mt) { i64 v_; is >> v_; mt = v_; return is; } }; template <__uint32_t mod> class static_modint32 { private: using mint = static_modint32<mod>; using i32 = __int32_t; using u32 = __uint32_t; using i64 = __int64_t; using u64 = __uint64_t; u32 v; constexpr inline u32 normalize(i64 v_) const { v_ %= mod; if (v_ < 0) { v_ += mod; } return v_; } public: constexpr static_modint32() : v(0) {} constexpr static_modint32(const i64& v_) : v(normalize(v_)) {} // operator static mint raw(u32 a){ mint m; m.v = a; return m; } constexpr u32 val() const { return v; } constexpr mint& operator+=(const mint& rhs) { v += rhs.val(); if (v >= mod) { v -= mod; } return (*this); } constexpr mint& operator-=(const mint& rhs) { v += mod - rhs.val(); if (v >= mod) { v -= mod; } return (*this); } constexpr mint& operator*=(const mint& rhs) { v = (u64)v * rhs.val() % mod; return (*this); } constexpr mint operator+(const mint& r) const { return mint(*this) += r; } constexpr mint operator-(const mint& r) const { return mint(*this) -= r; } constexpr mint operator*(const mint& r) const { return mint(*this) *= r; } constexpr mint& operator+=(const i64& rhs) { (*this) += mint(rhs); return (*this); } constexpr mint& operator-=(const i64& rhs) { (*this) -= mint(rhs); return (*this); } constexpr mint& operator*=(const i64& rhs) { (*this) *= mint(rhs); return (*this); } constexpr friend mint operator+(const i64& l, const mint& r) { return mint(l) += r; } constexpr friend mint operator-(i64 l, const mint& r) { return mint(l) -= r; } constexpr friend mint operator*(i64 l, const mint& r) { return mint(l) *= r; } constexpr mint operator+(i64 r) { return mint(*this) += r; } constexpr mint operator-(i64 r) { return mint(*this) -= r; } constexpr mint operator*(i64 r) { return mint(*this) *= r; } constexpr mint& operator=(i64 r) { return (*this) = mint(r); } constexpr bool operator==(const mint& r) const { return (*this).val() == r.val(); } template <typename T> constexpr mint pow(T e) const { mint ans(1), base(*this); while (e) { if (e & 1) { ans *= base; } base *= base; e >>= 1; } return ans; } constexpr inline mint inv() const { long long x, y; auto d = ext_gcd((long long)mod, (long long)v, x, y); assert(d == 1); return mint(y); } constexpr mint& operator/=(const mint& r) { return (*this) *= r.inv(); } constexpr mint operator/(const mint& r) const { return mint(*this) *= r.inv(); } constexpr friend mint operator/(const mint& l, i64 r) { return mint(l) /= mint(r); } constexpr friend mint operator/(i64 l, const mint& r) { return mint(l) /= mint(r); } // iostream constexpr friend std::ostream& operator<<(std::ostream& os, const mint& mt) { os << mt.val(); return os; } constexpr friend std::istream& operator>>(std::istream& is, mint& mt) { i64 v_; is >> v_; mt = v_; return is; } }; }; // namespace kyopro /// @brief modint /// @docs docs/math/static_modint.md #line 2 "library/src/template.hpp" #include<bits/stdc++.h> #define rep(i, N) for (int i = 0; i < (N); i++) #define all(x) (x).begin(),(x).end() #define popcount(x) __builtin_popcount(x) using i128=__int128_t; using ll = long long; using ld = long double; using graph = std::vector<std::vector<int>>; using P = std::pair<int, int>; constexpr int inf = 1e9; constexpr ll infl = 1e18; constexpr ld eps = 1e-6; const long double pi = acos(-1); constexpr uint64_t MOD = 1e9 + 7; constexpr uint64_t MOD2 = 998244353; constexpr int dx[] = { 1,0,-1,0 }; constexpr int dy[] = { 0,1,0,-1 }; template<class T>constexpr inline void chmax(T&x,T y){if(x<y)x=y;} template<class T>constexpr inline void chmin(T&x,T y){if(x>y)x=y;} #line 4 "main.cpp" using namespace std; using mint = atcoder::modint1000000007; constexpr int MAX = 3e5; mint fac[MAX], finv[MAX], inv[MAX]; const int NUM_FAC = 2000001; ll modfact(ll x) { static ll _fact[NUM_FAC + 1]; if (_fact[0] == 0) { _fact[0] = 1; for (int i = 1; i <= NUM_FAC; ++i) _fact[i] = _fact[i - 1] * i % MOD; } return _fact[x]; } ll modpow(ll a, ll n) { ll r = 1; while (n) r = r * ((n % 2) ? a : 1) % MOD, a = a * a % MOD, n >>= 1; return r; } ll moddiv(ll a, ll b) { ll ap_2 = modpow(b, MOD - 2); return (a * ap_2) % MOD; } ll aCb(ll a, ll b) { return moddiv(modfact(a), (modfact(a - b) * modfact(b)) % MOD); } int main() { ll n, m; cin >> n >> m; if (n < m) { puts("0"); return 0; } mint ans = 0; mint p = -1; for (int c = m; c >= 1; --c) { ans += (p *= -1) * aCb(m, c) * (mint(c).pow(n)); } cout << ans.val() << '\n'; }