結果
問題 | No.1035 Color Box |
ユーザー |
|
提出日時 | 2019-02-27 00:15:21 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 18 ms / 2,000 ms |
コード長 | 3,340 bytes |
コンパイル時間 | 718 ms |
コンパイル使用メモリ | 86,088 KB |
実行使用メモリ | 5,632 KB |
最終ジャッジ日時 | 2024-06-23 05:01:14 |
合計ジャッジ時間 | 2,225 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 36 |
ソースコード
#include <iostream>#include <fstream>#include <cmath>#include <cstdlib>#include <ctime>#include <algorithm>#include <numeric>#include <functional>#include <string>#include <vector>#include <bitset>#include <map>#include <set>#include <stack>#include <queue>#include <deque>using namespace std;using ll = long long;template<class T> using V = vector<T>;template<class T, class U> using P = pair<T, U>;#define REP(i,n) for(int i = 0; i < int(n); i++)#define FOR(i, m, n) for(int i = int(m);i < int(n);i++)#define ALL(obj) (obj).begin(),(obj).end()const ll MOD = (ll)1e9 + 7;const ll HINF = (ll)1e18;const ll LINF = (ll)1e9;const long double PI = 3.1415926535897932384626433;template<class T> void corner(bool flg, T hoge) {if (flg) {cout << hoge << endl;exit(0);}else return;}template <class T, class U>ostream &operator<<(ostream &o, const map<T, U>&obj) {o << "{"; for (auto &x : obj) o << " {" << x.first << " : " << x.second << "}" << ","; o << " }"; return o;}template <class T>ostream &operator<<(ostream &o, const set<T>&obj) {o << "{"; for (auto itr = obj.begin(); itr != obj.end(); ++itr) o << (itr != obj.begin() ? ", " : "") << *itr; o << "}"; return o;}template <class T>ostream &operator<<(ostream &o, const vector<T>&obj) {o << "{"; for (int i = 0; i < (int)obj.size(); ++i)o << (i > 0 ? ", " : "") <<obj[i]; o << "}"; return o;}template <class T, class U>ostream &operator<<(ostream &o, const pair<T, U>&obj) {o << "{" << obj.first << ", " << obj.second << "}"; return o;}template <template <class tmp> class T, class U> ostream &operator<<(ostream &o, const T<U> &obj) {o << "{"; for (auto itr = obj.begin(); itr != obj.end(); ++itr)o << (itr != obj.begin() ? ", " : "") << *itr; o << "}"; return o;}void print(void) {cout << endl;}template <class Head> void print(Head&& head) {cout << head;print();}template <class Head, class... Tail> void print(Head&& head, Tail&&... tail) {cout << head << " ";print(forward<Tail>(tail)...);}template <class T> void chmax(T& a, const T b) { a = max<T>(a, b); }template <class T> void chmin(T& a, const T b) { a = min<T>(a, b); }void YN(bool flg) {cout << ((flg) ? "YES" : "NO") << endl;}void Yn(bool flg) {cout << ((flg) ? "Yes" : "No") << endl;}void yn(bool flg) {cout << ((flg) ? "yes" : "no") << endl;}//Combination Modclass Combination_Mod {public:vector<long long> fac, finv, inv;long long MOD;Combination_Mod(int N, long long mod) : fac(vector<long long>(N + 1)), finv(vector<long long>(N + 1)), inv(vector<long long>(N + 1)), MOD(mod) {fac[0] = fac[1] = finv[0] = finv[1] = inv[1] = 1;for (int i = 2; i <= N; ++i) {fac[i] = fac[i - 1] * i % MOD;inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;finv[i] = finv[i - 1] * inv[i] % MOD;}}long long num(int n, int k) {return ((n < 0 || k < 0 || n < k) ? 0 : fac[n] * (finv[k] * finv[n - k] % MOD) % MOD);}};//Pow_Mod O(log(n))long long Pow_Mod(long long x, long long n, long long mod) {long long res = 1;for (; n > 0; n >>= 1, (x *= x) %= mod) if (n & 1) (res *= x) %= mod;return res;}int main() {ll N, M; cin >> N >> M;Combination_Mod CM(M,MOD);ll ans = 0,sgn = 1;for(ll i = M; 1 <= i; --i){(ans += (MOD + sgn*( (CM.num(M, i)*Pow_Mod(i, N, MOD)) % MOD ) )%MOD ) %= MOD;sgn *= -1;}cout << ans << endl;return 0;}