結果
問題 | No.1035 Color Box |
ユーザー |
![]() |
提出日時 | 2020-04-24 23:11:32 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 24 ms / 2,000 ms |
コード長 | 4,001 bytes |
コンパイル時間 | 1,546 ms |
コンパイル使用メモリ | 168,544 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-10-15 03:45:16 |
合計ジャッジ時間 | 2,765 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 36 |
ソースコード
#include <bits/stdc++.h>#define REP(i, n) for(int i = 0; (i) < (n); (i)++)#define INF 5000000000000000using namespace std;struct Edge{int to;long weight;Edge(int t, long w) : to(t), weight(w) {}};long modpow(long a, long n, long mod) {long res = 1;while (n > 0) {if (n & 1) res = res * a % mod;a = a * a % mod;n >>= 1;}return res;}// a^{-1} mod を計算するlong modinv(long a, long mod) {return modpow(a, mod - 2, mod);}struct compare1 {bool operator()(const pair<long, long>& value,const long& key){return (value.first < key);}bool operator()(const long& key,const pair<long, long>& value){return (key < value.first);}};struct UnionFind {vector<int> par;vector<int> rank;UnionFind(int n = 1){init(n);}void init(int n = 1){par.resize(n);rank.resize(n);REP(i, n) par[i] = i, rank[i] = 0;}int root(int x){if(par[x] == x) return x;else return par[x] = root(par[x]);}bool issame(int x, int y){return root(x) == root(y);}bool merge(int x, int y){x = root(x); y = root(y);if(x == y) return false;if(rank[x] < rank[y]) swap(x, y);if(rank[x] == rank[y]) rank[x]++;par[y] = x;return true;}};template<class Abel> struct weightedUnionFind{vector<int> par;vector<int> rank;vector<Abel> diff_weight;weightedUnionFind(int n = 1, Abel SUM_UNITY = 0){init(n, SUM_UNITY);}void init(int n = 1, Abel SUM_UNITY = 0){par.resize(n); rank.resize(n); diff_weight.resize(n);REP(i, n) par[i] = i, rank[i] = 0, diff_weight[i] = SUM_UNITY;}int root(int x){if(par[x] == x) return x;else{int r = root(par[x]);diff_weight[x] += diff_weight[par[x]];return par[x] = r;}}Abel weight(int x){root(x);return diff_weight[x];}bool issame(int x, int y){return root(x) == root(y);}bool merge(int x, int y, Abel w){w += weight(x); w -= weight(y);x = root(x); y = root(y);if(x == y) return false;if(rank[x] < rank[y]) swap(x, y), w = -w;if(rank[x] == rank[y]) rank[x]++;par[y] = x;diff_weight[y] = w;return true;}Abel diff(int x, int y){return weight(y) - weight(x);}};using Graph = vector<vector<int>>;using P = pair<long, long>;/*void dijkstra(int s, int V, Graph &G, long* d){priority_queue<P, vector<P>, greater<P>> pque;fill(d, d + V, INF);d[s] = 0;pque.push(P(0, s));while(!pque.empty()){P p = pque.top(); pque.pop();int now = p.second;if(d[now] < p.first) continue;REP(i, G[now].size()){Edge e = G[now][i];if(d[e.to] > d[now] + e.weight){d[e.to] = d[now] + e.weight;pque.push(P(d[e.to], e.to));}}}}*/long GCD(long a, long b){if(b == 0l) return a;if(a < b) return GCD(b, a);else return GCD(b, a%b);}int main(){long N, M; cin >> N >> M;long kai[100005], kai2[100005];long mod = 1000000007;kai[0] = 1l;kai2[0] = 1l;for(long i = 1l; i <= M; i++){kai[i] = (i * kai[i-1l]) % mod;kai2[i] = (modinv(i, mod) * kai2[i-1l]) % mod;}long ans = 0l;for(long i = 0l; i <= M; i++){long temp = kai[M] * kai2[i]; temp %= mod;temp *= kai2[M-i]; temp %= mod;temp *= modpow(M-i, N, mod); temp %= mod;if(i%2==0){ans += temp;ans %= mod;}else{ans -= temp;if(ans < 0l) ans += mod;}}cout << ans << endl;return 0;}