結果
問題 | No.2817 Competition |
ユーザー |
|
提出日時 | 2024-07-17 03:46:14 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 504 ms / 2,000 ms |
コード長 | 9,485 bytes |
コンパイル時間 | 4,745 ms |
コンパイル使用メモリ | 252,124 KB |
実行使用メモリ | 14,848 KB |
最終ジャッジ日時 | 2024-07-17 03:46:27 |
合計ジャッジ時間 | 11,841 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 24 |
コンパイルメッセージ
main.cpp: In function 'std::ostream& operator<<(std::ostream&, const std::map<T, S>&)': main.cpp:198:16: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions] 198 | for (auto &[key, val] : m) | ^
ソースコード
#include <bits/stdc++.h>using namespace std;#include <atcoder/all>using namespace atcoder;using ll = long long;using ld = long double;using pii = pair<int, int>;using pli = pair<ll, int>;using pll = pair<ll, ll>;typedef vector<ll> vi;typedef vector<vi> vvi;const string Yes = "Yes";const string No = "No";const string YES = "YES";const string NO = "NO";const string abc = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";const ll MOD = 1000000007;const ll mod = 998244353;const long long inf = 1LL << 60;const long double PI = 3.141592653589793;#pragma GCC target("avx2")#pragma GCC optimize("O3")#pragma GCC optimize("unroll-loops")#define _GLIBCXX_DEBUG#define pb push_back#define mp make_pair#define all(x) (x).begin(), (x).end()#define fi first#define se secondconst vector<int> dx = {0, 1, 0, -1};const vector<int> dy = {1, 0, -1, 0};using mint = modint998244353;using Mint = modint1000000007;#define YESNO(T) \if (T) \{ \cout << "YES" << endl; \} \else \{ \cout << "NO" << endl; \}#define yesno(T) \if (T) \{ \cout << "yes" << endl; \} \else \{ \cout << "no" << endl; \}#define YesNo(T) \if (T) \{ \cout << "Yes" << endl; \} \else \{ \cout << "No" << endl; \}#define inV(vec) \for (ll i = 0; i < vec.size(); i++) \cin >> vec[i];#define outV(vec) \for (ll i = 0; i < vec.size(); i++) \{ \cout << vec[i] << " "; \} \cout << endl;#define print(s) cout << s << endl;#define updiv(n, x) (n + x - 1) / x#define rounddiv(n, x) (ll)((double)(n) / (double)(x) + 0.5)#define fix(n) fixed << setprecision(n);#define ioinit \ios::sync_with_stdio(false); \std::cin.tie(nullptr)template <typename T>inline bool chmax(T &a, T b) { return ((a < b) ? (a = b, true) : (false)); }template <typename T>inline bool chmin(T &a, T b) { return ((a > b) ? (a = b, true) : (false)); }template <class T>ll sum(const T &a) { return accumulate(all(a), 0LL); }#pragma region inout// pair_outtemplate <typename T, typename U>ostream &operator<<(ostream &os, const pair<T, U> &p){os << p.first << " " << p.second;return os;}// pair_intemplate <typename T, typename U>istream &operator>>(istream &is, pair<T, U> &p){is >> p.first >> p.second;return is;}// vector_outtemplate <typename T>ostream &operator<<(ostream &os, const vector<T> &v){int s = (int)v.size();for (int i = 0; i < s; i++)os << (i ? " " : "") << v[i];return os;}// vector_intemplate <typename T>istream &operator>>(istream &is, vector<T> &v){for (auto &x : v)is >> x;return is;}//__int128_t_inistream &operator>>(istream &is, __int128_t &x){string S;is >> S;x = 0;int flag = 0;for (auto &c : S){if (c == '-'){flag = true;continue;}x *= 10;x += c - '0';}if (flag)x = -x;return is;}//__uint128_t_inistream &operator>>(istream &is, __uint128_t &x){string S;is >> S;x = 0;for (auto &c : S){x *= 10;x += c - '0';}return is;}//__int128_t_outostream &operator<<(ostream &os, __int128_t x){if (x == 0)return os << 0;if (x < 0)os << '-', x = -x;string S;while (x)S.push_back('0' + x % 10), x /= 10;reverse(begin(S), end(S));return os << S;}//__uint128_t_outostream &operator<<(ostream &os, __uint128_t x){if (x == 0)return os << 0;string S;while (x)S.push_back('0' + x % 10), x /= 10;reverse(begin(S), end(S));return os << S;}// vector<vector>_outtemplate <typename T>ostream &operator<<(ostream &os, const vector<vector<T>> &v){for (int i = 0; i < (int)v.size(); i++){os << v[i] << endl;}return os;}// vector<vector<vector>>_outtemplate <typename T>ostream &operator<<(ostream &os, const vector<vector<vector<T>>> &v){for (int i = 0; i < (int)v.size(); i++){os << "i = " << i << endl;os << v[i];}return os;}// map_outtemplate <typename T, typename S>ostream &operator<<(ostream &os, const map<T, S> &m){for (auto &[key, val] : m){os << key << ":" << val << " ";}return os;}// set_outtemplate <typename T>ostream &operator<<(ostream &os, const set<T> &st){auto itr = st.begin();for (int i = 0; i < (int)st.size(); i++){os << *itr << (i + 1 != (int)st.size() ? " " : "");itr++;}return os;}// multiset_outtemplate <typename T>ostream &operator<<(ostream &os, const multiset<T> &st){auto itr = st.begin();for (int i = 0; i < (int)st.size(); i++){os << *itr << (i + 1 != (int)st.size() ? " " : "");itr++;}return os;}// queue_outtemplate <typename T>ostream &operator<<(ostream &os, queue<T> q){while (q.size()){os << q.front() << " ";q.pop();}return os;}// deque_outtemplate <typename T>ostream &operator<<(ostream &os, deque<T> q){while (q.size()){os << q.front() << " ";q.pop_front();}return os;}// stack_outtemplate <typename T>ostream &operator<<(ostream &os, stack<T> st){while (st.size()){os << st.top() << " ";st.pop();}return os;}// priority_queue_outtemplate <class T, class Container, class Compare>ostream &operator<<(ostream &os, priority_queue<T, Container, Compare> pq){while (pq.size()){os << pq.top() << " ";pq.pop();}return os;}#if __has_include(<atcoder/all>)// 998244353_inistream &operator>>(istream &a, mint &b){long long tmp;a >> tmp;b = tmp;return a;}// 998244353_outostream &operator<<(ostream &a, mint &b){a << b.val();return a;}// 1000000007_inistream &operator>>(istream &a, Mint &b){long long tmp;a >> tmp;b = tmp;return a;}// 1000000007_outostream &operator<<(ostream &a, Mint &b){a << b.val();return a;}#endif#pragma endregion inout// 繰り返し二乗法ll modpow(ll a, ll n, ll mod){if (a == 0){return 0;}ll res = 1;while (n > 0){if (n & 1)res = res * a % mod;a = a * a % mod;n >>= 1;}return res;}// 割り算ll Div(ll a, ll b, ll m){return (a * modpow(b, m - 2, m)) % m;}// 階乗vector<ll> fact(1);void fac(ll N, ll m){fact[0] = 1;for (int i = 1; i <= N; i++){ll ppp = i;while (ppp % m == 0){ppp /= m;}fact.pb(fact[i - 1] * (ppp));fact[i] %= m;}}ll v(ll n, ll p){ll aaans = 0;ll nppp = n;while (nppp > 0){aaans += nppp / p;nppp /= p;}return aaans;}// 組み合わせll comb(ll n, ll r, ll m){if (n < r){return 0;}if (r < 0){return 0;}if (n < 0){return 0;}return Div(fact[n], fact[r] * fact[n - r] % m, m);}ll mex(ll a, ll b){if (a > b){swap(a, b);}if (a != 0){return 0;}else{if (b != 1){return 1;}else{return 2;}}}template <typename T>struct Edge{int to;T cost;};using Graph = vector<vector<Edge<long long>>>; // cost の型を long long に指定/* tree_diamiter : dfs を用いて重み付き木 T の直径を求める計算量: O(N)*/template <typename T>pair<T, int> dfs(const Graph &G, int u, int par){ // 最遠点間距離と最遠点を求めるpair<T, int> ret = make_pair((T)0, u);for (auto e : G[u]){if (e.to == par)continue;auto next = dfs<T>(G, e.to, u);next.first += e.cost;ret = max(ret, next);}return ret;}template <typename T>T tree_diamiter(const Graph &G){pair<T, int> p = dfs<T>(G, 0, -1);pair<T, int> q = dfs<T>(G, p.second, -1);return q.first;}ll di(pll a,pll b){return (a.fi-b.fi)*(a.fi-b.fi)+(a.se-b.se)*(a.se-b.se);}ll gcd(ll x, ll y) {if (y == 0) {return x;}else {return gcd(y, x % y);}}int main(){queue<vector<ll>>q;ll N;cin>>N;for(int i=0;i<N;i++){ll A;cin>>A;q.push({1,A});}while(q.size()>1){vector<ll>a=q.front();q.pop();vector<ll>b=q.front();q.pop();vector<ll>c=convolution(a,b);q.push(c);}vector<ll>ans=q.front();mint finans=0;for(int i=1;i<ans.size();i++){finans+=ans[i]*modpow(i,N-i,mod);}print(finans);}