結果
| 問題 | No.391 CODING WAR |
| ユーザー |
 AC2K
|
| 提出日時 | 2023-05-05 00:08:24 |
| 言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 48 ms / 2,000 ms |
| コード長 | 9,749 bytes |
| コンパイル時間 | 5,226 ms |
| コンパイル使用メモリ | 308,824 KB |
| 実行使用メモリ | 22,784 KB |
| 最終ジャッジ日時 | 2024-11-22 13:23:10 |
| 合計ジャッジ時間 | 6,772 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 4 |
| other | AC * 16 |
ソースコード
#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_)) {}// operatorconstexpr 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);}// iostreamconstexpr 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_)) {}// operatorstatic 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);}// iostreamconstexpr 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';}