結果
問題 | No.1035 Color Box |
ユーザー |
|
提出日時 | 2020-04-24 21:44:35 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 57 ms / 2,000 ms |
コード長 | 2,019 bytes |
コンパイル時間 | 1,490 ms |
コンパイル使用メモリ | 169,972 KB |
実行使用メモリ | 10,368 KB |
最終ジャッジ日時 | 2024-10-15 02:39:00 |
合計ジャッジ時間 | 3,382 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 36 |
ソースコード
#include <bits/stdc++.h>using namespace std;template<int MAX>struct Combination {vector<long long> _inv, _fac, _ifac;const long long MOD;Combination(long long mod) : _inv(MAX+1), _fac(MAX+1), _ifac(MAX+1), MOD(mod) { init(); }inline void init(long long mod = 0) { init_inv(), init_fac(); }inline void init_inv() {_inv[0] = 0;for (int i = 1; i <= MAX; i++) {if (i == 1) _inv[i] = 1;else {_inv[i] = (MOD - (MOD / i) * _inv[MOD % i]) % MOD;if (_inv[i] < 0) _inv[i] += MOD;}}}inline void init_fac() {_fac[0] = _ifac[0] = 1;for (int i = 1; i <= MAX; i++) {_fac[i] = _fac[i-1] * i % MOD;_ifac[i] = _ifac[i-1] * _inv[i] % MOD;}}inline long long modpow(long long n, long long r) {n %= MOD, r %= (MOD-1);if (!n) return 0;long long ret = 1; long long tmp = n;while (r != 0) {if (r % 2) ret *= tmp;tmp *= tmp; tmp %= MOD; ret %= MOD;r /= 2;}return ret;}inline const long long invb(int i) { return (i <= MAX) ? _inv[i] : this->modpow(i, MOD-2); }inline const long long inv(int i) { return _inv[i]; }inline const long long fac(int i) { return _fac[i]; }inline const long long ifac(int i) { return _ifac[i]; }const long long operator()(int n, int r) {if (n < r) return 0;return fac(n) * ifac(r) % MOD * ifac(n-r) % MOD;}};int main() {cin.tie(nullptr);ios::sync_with_stdio(false);constexpr int MAX = 300000;constexpr int mod = 1000000007;Combination<MAX> C(mod);long long m, n; cin >> n >> m;long long ans = C.modpow(m, n);for (int i = 1; i <= m-1; i++) {if (i & 1) ans -= C.modpow(m-i, n) * C(m, m-i) % mod;else ans += C.modpow(m-i, n) * C(m, m-i) % mod;}cout << (ans % mod + mod) % mod << "\n";return 0;}