結果
問題 | No.1237 EXP Multiple! |
ユーザー | laoidn |
提出日時 | 2023-03-27 11:15:06 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 95 ms / 2,000 ms |
コード長 | 9,325 bytes |
コンパイル時間 | 4,109 ms |
コンパイル使用メモリ | 243,912 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-09-19 10:10:12 |
合計ジャッジ時間 | 6,059 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 68 ms
5,376 KB |
testcase_02 | AC | 92 ms
5,376 KB |
testcase_03 | AC | 95 ms
5,376 KB |
testcase_04 | AC | 89 ms
5,376 KB |
testcase_05 | AC | 34 ms
5,376 KB |
testcase_06 | AC | 33 ms
5,376 KB |
testcase_07 | AC | 35 ms
5,376 KB |
testcase_08 | AC | 33 ms
5,376 KB |
testcase_09 | AC | 34 ms
5,376 KB |
testcase_10 | AC | 33 ms
5,376 KB |
testcase_11 | AC | 33 ms
5,376 KB |
testcase_12 | AC | 33 ms
5,376 KB |
testcase_13 | AC | 34 ms
5,376 KB |
testcase_14 | AC | 33 ms
5,376 KB |
testcase_15 | AC | 33 ms
5,376 KB |
testcase_16 | AC | 33 ms
5,376 KB |
testcase_17 | AC | 34 ms
5,376 KB |
testcase_18 | AC | 33 ms
5,376 KB |
testcase_19 | AC | 33 ms
5,376 KB |
ソースコード
#include <bits/stdc++.h> using namespace std; #include <atcoder/all> using namespace atcoder; #include <iostream> #include <vector> using ll = long long; using ld = long double; using P = pair<int, int>; using Graph = vector<vector<int>>; using vi = vector<int>; using vl = vector<long>; using vll = vector<long long>; using vb = vector<bool>; using vvi = vector<vi>; using vvl = vector<vl>; using vvb = vector<vb>; using vdouble = vector<double>; using vvdouble = vector<vdouble>; using vvvdouble = vector<vvdouble>; using vvll = vector<vll>; using vvvll = vector<vvll>; using vc = vector<char>; using vvc = vector<vc>; using vs = vector<string>; using pii = pair<long long, long long>; const long double EPS = 1e-10; const long long INF = 1e18; const long double PI = acos(-1.0L); #define reps(i, a, n) for (ll i = (a); i < (ll)(n); i++) #define rep(i, n) for (ll i = (0); i < (ll)(n); i++) #define rrep(i, n) for (ll i = (1); i < (ll)(n + 1); i++) #define repd(i, n) for (ll i = n - 1; i >= 0; i--) #define rrepd(i, n) for (ll i = n; i >= 1; i--) #define ALL(n) begin(n), end(n) #define fore(i, a) for (auto &i : a) #define IN(a, x, b) (a <= x && x < b) #define IN(a, x, b) (a <= x && x < b) #define INIT \ std::ios::sync_with_stdio(false); \ std::cin.tie(0); template <class T> inline T CHMAX(T &a, const T b) { return a = (a < b) ? b : a; } template <class T> inline T CHMIN(T &a, const T b) { return a = (a > b) ? b : a; } #include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound #include <bitset> // bitset #include <cctype> // isupper, islower, isdigit, toupper, tolower #include <cstdint> // int64_t, int*_t #include <cstdio> // printf #include <deque> // deque #include <iostream> // cout, endl, cin #include <map> // map #include <queue> // queue, priority_queue #include <set> // set #include <stack> // stack #include <string> // string, to_string, stoi #include <tuple> // tuple, make_tuple #include <unordered_map> // unordered_map #include <unordered_set> // unordered_set #include <utility> // pair, make_pair #include <vector> // vector using namespace std; ll GCD(ll m, ll n) { // ベースケース if (n == 0) return m; // 再帰呼び出し return GCD(n, m % n); } ll minlong = 0; long long Power(long long a, long long b, long long m) { long long p = a, Answer = 1; p %= m; for (int i = 0; i < 63; i++) { ll wari = (1LL << i); if ((b / wari) % 2 == 1) { Answer %= m; Answer = (Answer * p) % m; // 「a の 2^i 乗」が掛けられるとき } ll t = p % m; p = (t * t) % m; // cout << p << endl; } return Answer; } // a ÷ b を m で割った余りを返す関数 long long Division(long long a, long long b, long long m) { return (a * Power(b, m - 2, m)) % m; } // nCr mod 1000000007 を返す関数 long long nCk(ll n, ll r) { const long long M = 1000000007; // 手順 1: 分子 a を求める long long a = 1; for (int i = 1; i <= n; i++) a = (a * i) % M; // 手順 2: 分母 b を求める long long b = 1; for (int i = 1; i <= r; i++) b = (b * i) % M; for (int i = 1; i <= n - r; i++) b = (b * i) % M; // 手順 3: 答えを求める return Division(a, b, M); } using Interval = pair<ll, ll>; // nCk mint を返す関数。 ll modnCk(ll n, ll r) { ll a = 1; for (ll i = n; i > n - r; i--) { a *= i; a /= n + 1 - i; } return a; } // 終点時間でsortをかけるのに必要(区間スケジューリング問題など) bool cmp(const Interval &a, const Interval &b) { return a.second < b.second; } vll dycstra(vector<vector<pair<ll, ll>>> G, ll N, ll K) { vb kaku(N, false); vll cur(N, INF); cur[K] = 0; priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> Q; Q.push(make_pair(cur[K], K)); while (!Q.empty()) { ll pos = Q.top().second; Q.pop(); if (kaku[pos]) continue; kaku[pos] = true; for (ll i = 0; i < G[pos].size(); i++) { ll nex = G[pos][i].first; ll cost = G[pos][i].second; if (cur[nex] > cur[pos] + cost) { cur[nex] = cur[pos] + cost; Q.push(make_pair(cur[nex], nex)); } } } return cur; } ll f(ll x, vll &memo, ll D, vector<pair<ll, ll>> &X) { if (memo[x] != -1) return memo[x]; if (x < D) return 0; ll y = x - D; ll x1, x2, y1, y2; tie(x1, y1) = X[y]; tie(x2, y2) = X[x]; ll cost = abs(x1 - x2) + abs(y1 - y2); ll res = cost + f(y, memo, D, X); return memo[x] = res; } template <class T> struct BIT { int n; // 要素数 vector<T> bit[2]; // データの格納先 BIT(int n_) { init(n_); } void init(int n_) { n = n_ + 1; for (int p = 0; p < 2; p++) bit[p].assign(n, 0); } void add_sub(int p, int i, T x) { for (int idx = i; idx < n; idx += (idx & -idx)) { bit[p][idx] += x; } } void add(int l, int r, T x) { // [l,r) に加算 add_sub(0, l, -x * (l - 1)); add_sub(0, r, x * (r - 1)); add_sub(1, l, x); add_sub(1, r, -x); } T sum_sub(int p, int i) { T s(0); for (int idx = i; idx > 0; idx -= (idx & -idx)) { s += bit[p][idx]; } return s; } T sum(int i) { return sum_sub(0, i) + sum_sub(1, i) * i; } // sum'(i)=sum(i)-x(l-i)+xi(sum'(i)は加算後の合計値sum(i)測酸前の合計値) T query(int l, int r) { return sum(r - 1) - sum(l - 1); } // 任意の区間を計算することが可能これは[l,r)の区間和を計算している。 int lower_bound(T w) { // a_1 + a_2 + ... + a_x >= w となるような最小の x // を求める(ただし a_i >= 0) if (w <= 0) { return 0; } else { int x = 0, r = 1; while (r < n) r = r << 1; for (int len = r; len > 0; len = len >> 1) { // 長さlenは1段下るごとに半分に if (x + len < n && bit[x + len] < w) { // 採用するとき w -= bit[x + len]; x += len; } } return x + 1; } } }; vll BFS(vvll &G, ll &x) { vll cut(G.size(), INF); queue<ll> Q; Q.push(x); cut[x] = 0; while (!Q.empty()) { ll a = Q.front(); Q.pop(); rep(i, G[a].size()) { if (cut[G[a][i]] > cut[a] + 1) { cut[G[a][i]] = cut[a] + 1; Q.push(G[a][i]); } } } return cut; } template <class Abel> struct UnionFind { vector<int> par; vector<int> rank; vector<Abel> diff_weight; vector<int> siz; UnionFind(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); siz.resize(n); for (int i = 0; i < n; ++i) par[i] = i, rank[i] = 0, diff_weight[i] = SUM_UNITY, siz[i] = 1; } 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); // 通常時も同じ } // weight(y) - weight(x) = w となるように merge する bool merge(int x, int y, Abel w) { // x と y それぞれについて、 root との重み差分を補正 w += weight(x); w -= weight(y); // x と y の root へ (x と y が既につながっていたら false を返すようにした) x = root(x); y = root(y); if (x == y) return false; // rank[x] >= rank[y] となるように x と y を swap (それに合わせて w // も符号反転します)これはUnion by // rankと呼ばれ根の高さをO(logN)で抑えられる手法である。 if (rank[x] < rank[y]) swap(x, y), w = -w; // y (のroot) を x (のroot) // の下にくっつける(高さが低い方の根付き木を高いほうに併合する) if (rank[x] == rank[y]) ++rank[x]; siz[x] += siz[y]; par[y] = x; // x が y の親になるので、x と y の差分を diff_weight[y] に記録 diff_weight[y] = w; return true; } Abel diff(int x, int y) { return weight(y) - weight(x); } int size(int x) { return siz[root(x)]; } }; void Yes(bool b) { if (b) cout << "Yes" << endl; else cout << "No" << endl; } void YES(bool b) { if (b) cout << "YES" << endl; else cout << "NO" << endl; } vector<long long> yaku(long long n) { vector<long long> ret; for (long long i = 1; i * i <= n; i++) { if (n % i == 0) { ret.push_back(i); if (i * i != n) ret.push_back(n / i); } } sort(ret.begin(), ret.end()); // 昇順に並べる return ret; } // #include <atcoder/lazysegtree>用 int main() { ll N, M, K; cin >> N; vll A(N); rep(i, N) { cin >> A[i]; } sort(ALL(A)); if (A[0] == 0) { cout << -1 << endl; return 0; } if (A[N - 1] >= 4) { cout << 1000000007 << endl; return 0; } ll count = 1; vll B(4); B[1] = 1; B[2] = 4; B[3] = 729; rep(i, N) { count *= B[A[i]]; if (count > 1000000007) { cout << 1000000007 << endl; return 0; } } cout << 1000000007 % count << endl; }