結果
問題 | No.2729 Addition and Multiplication in yukicoder (Easy) |
ユーザー |
|
提出日時 | 2024-04-19 21:32:55 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 54 ms / 2,000 ms |
コード長 | 34,244 bytes |
コンパイル時間 | 3,686 ms |
コンパイル使用メモリ | 245,968 KB |
最終ジャッジ日時 | 2025-02-21 03:48:49 |
ジャッジサーバーID (参考情報) |
judge2 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 18 |
ソースコード
/*#include <bits/stdc++.h>using namespace std;int main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);*/// __builtin_popcountll() ;// multiset ;// unordered_set ;// unordered_map ;// reverse ;// substr// assert// to_string// is_sorted/*#include <atcoder/all>using namespace atcoder ;// using mint = modint;// using mint = modint998244353 ;// using mint = modint1000000007 ;*/#include <bits/stdc++.h>using namespace std;/*#include<boost/multiprecision/cpp_int.hpp>using namespace boost::multiprecision;typedef cpp_int cp ;cp cp_mod0 = 1000000007 ;cp cp_mod1 = 998244353 ;cp cp_binpower(cp a, cp b ,cp c){if(b == 0)return 1 ;a %= c ;cp d = cp_binpower(a,b/2,c) ;(d *= d) %= c ;if(b%2) (d *= a) %= c ;return d ;}cp cp_powpow(cp A, cp B){if(B == 0)return 1 ;if(B == 1)return A ;cp res = 1 ;for(cp i = 1 ;i <= B ;i ++)res *= A ;return res ;}string cp_10_to_2(cp X){string abc = "" ;if(X == 0)return "0" ;while(X > 0){abc = char(X%2 + '0') + abc ;X /= 2 ;}return abc ;}cp cp_2_to_10(string moji){cp abc = 0 ;cp K = moji.size() ;for(long long i = 0 ; i < K ; i++){long long x = moji[i] - '0' ;abc = abc * 2 + cp(x) ;}return abc ;}*///-------型-------typedef long long ll;typedef string st ;typedef long double ld ;typedef unsigned long long ull ;using P = pair<ll,ll> ;using Edge = tuple<ll,ll,ll> ;using AAA = tuple<ll,ll,ll,ll> ;template<typename T>using V = vector<T> ;template<typename T>using VV = vector<vector<T>> ;template<typename T>using VVV = vector<vector<vector<T>>> ;template<typename T>using VVVV = vector<vector<vector<vector<T>>>> ;//-------型-------//-------定数-------const ll mod0 = 1000000007;const ll mod1 = 998244353 ;const ll LINF = 5000000000000000000+2 ; //(10^18) + 2const ld pai = acos(-1) ;const ld EPS = 1e-10 ;//-------定数-------//-------マクロ-------#define pb push_back#define fpb(A,x,n) A.insert(A.begin()+x,n) ;#define ppb pop_back#define pf push_front#define ppf pop_front#define all(x) x.begin(), x.end()#define rep(i,a,n) for (ll i = a; i <= (n); ++i)#define rrep(i,a,b,c) for (ll i = a ; i <= (b) ; i += c)#define ketu(i,a,n) for (ll i = a; i >= (n); --i)#define re return 0;#define fore(i,a) for(auto &i:a)#define fi first#define se second#define C cout#define E "\n";#define EE endl;//-------マクロ-------//-------テンプレ文字列-------st zz = "abcdefghijklmnopqrstuvwxyz" ;st ZZ = "ABCDEFGHIJKLMNOPQRSTUVWXYZ" ;st tintin = "%" ;st Y = "Yes" ;st YY = "No" ;st KU = " " ;//-------テンプレ文字列-------template<typename T>void chmin(T& x ,T y){x = min(x,y) ;}template<typename T>void chmax(T& x ,T y){x = max(x,y) ;}vector<ll> Y4 = {0,1,0,-1} ;vector<ll> X4 = {1,0,-1,0} ;vector<ll> Y8 = {0,1,1,1,0,-1,-1,-1} ;vector<ll> X8 = {1,1,0,-1,-1,-1,0,1} ;ll max_element(V<ll> &A){ll res = *max_element(all(A)) ;return res ;}ll max_element_index(V<ll> &A){ll res = max_element(all(A)) - A.begin() ;return res ;}ll min_element(V<ll> &A){ll res = *min_element(all(A)) ;return res ;}ll min_element_index(V<ll> &A){ll res = min_element(all(A)) - A.begin() ;return res ;}ll Random_Number(ll a , ll b){random_device rd ;mt19937 gen(rd()) ;uniform_int_distribution<ll> dis(a,b);ll res = dis(gen) ;return res ;}ll sum_V(V<ll> A){ll N = A.size() ;ll res = 0 ;rep(i,0,N-1){res += A[i] ;}return res ;}ll sum_D(deque<ll> A){deque<ll> B = A ;ll res = 0 ;while(!B.empty()){ll pos = B.front() ;B.ppf() ;res += pos ;}return res ;}ll sum_Q(queue<ll> Q){queue<ll> B = Q ;ll res = 0 ;while(!B.empty()){ll pos = B.front() ;B.pop() ;res += pos ;}return res ;}ll k_lcm(V<ll> A){ll res = 1 ;ll N = A.size() ;rep(i,0,N-1){ll ans ;ll K = A[i] / gcd(res,A[i]) ;bool p = __builtin_smulll_overflow(res,K,&ans) ;if(p == true)return -1 ;else res = res * K ;}return res ;}ll k_gcd(V<ll> A){ll N = A.size() ;ll res = 0 ;rep(i,0,N-1){res = gcd(res,A[i]) ;}return res ;}V<ll> sort_erase_unique(V<ll> &A){sort(all(A)) ;A.erase(unique(all(A)),A.end()) ;return A ;}ll powpow(ll A , ll B){if(B == 0)return 1 ;if(B == 1)return A ;ll res = 1 ;rep(i,1,B){res *= A ;}return res ;}ll Ceil(ll a , ll b){if(a >= 0) return (a + b - 1) / b ;else return a / b ;}ll Floor(ll a , ll b){if(a >= 0) return a / b ;else return (a - b + 1) / b ;}ll range_multiple_count(ll l, ll r, ll x){return r / x - (l + x - 1) / x + 1 ;}ll Permutation(ll N){if(N == 0)return 1 ;ll res = 1 ;rep(i,1,N)res *= i ;return res ;}V<st> String_Next_Permutation(st N){sort(all(N)) ;ll M = N.size() ;ll Size = Permutation(M) ;V<st> res(Size) ;ll count = 0 ;do{rep(i,0,M-1){res[count].pb(N[i]) ;}count ++ ;}while(next_permutation(N.begin(),N.end()));return res ;}V<V<ll>> Vector_Next_Permutation(V<ll> A){ll Size = Permutation(A.size()) ;V<V<ll>> res(Size) ;ll count = 0 ;do{fore(u,A){res[count].pb(u) ;}count ++ ;}while(next_permutation(A.begin(),A.end()));return res ;}st Sub(st A,ll l , ll r){st res ;rep(i,l,r){res += A[i] ;}return res ;}st reading_x(st s , ll Size , ll n , ll lr){if(s.size() >= Size)return s ;st res = "" ;st x = to_string(n) ;if(lr == 0){while(s.size() + res.size() < Size)res += x ;res += s ;}else{res = s ;while(s.size() + res.size() < Size)res += x ;}return res ;}ll Arithmetic_Sequence(ll l , ll r){ll res = 0 ;if(l == 0)l ++ ;if(l == r)return l ;res += r*(r+1)/2 ;res -= l*(l-1)/2 ;return res ;}bool Crossing_Section(P A,P B){bool res = true ;if(A.fi > B.fi)swap(A,B) ;if(A.se < B.fi || B.se < A.fi)res = false ;return res ;}template<typename T>V<T> array_sub(V<T> A,ll l , ll r){V<T> res ;rep(i,l,r){res.pb(A[i]) ;}return res ;}template<typename T>V<T> sr(V<T> A){sort(all(A)) ;reverse(all(A)) ;return A ;}template<typename T>V<T> shift_left(V<T> A, ll k){ll N = A.size() ;k %= N ;V<T> res(N) ;rep(i,0,N-1){res[i] = A[(i+k)%N] ;}return res ;}template<typename T>V<T> shift_right(V<T> A , ll k){ll N = A.size() ;k %= N ;V<T> res(N) ;rep(i,0,N-1){res[i] = A[(i-k+N)%N] ;}return res ;}template<typename T>void debag_1V_kaigyou(V<T> A){ll N = A.size() ;rep(i,0,N-1){C << A[i] << E}}template<typename T>void debag_1V_space(V<T> A){ll N = A.size() ;rep(i,0,N-1){C << A[i] << KU ;}C << E}void debag_2V(V<V<ll>> A){ll N = A.size() ;rep(i,0,N-1){ll M = A[i].size() ;rep(j,0,M-1){if(A[i][j] == LINF || A[i][j] == -LINF)C << "L" << KU ;else C << A[i][j] << KU ;}C << E}}template<typename T>void debag_2V_other(V<V<T>> A){ll N = A.size() ;rep(i,0,N-1){ll k = A[i].size() ;rep(j,0,k-1){C << A[i][j] << KU ;}C << E}}void debag_pair(V<P> A){ll N = A.size() ;rep(i,0,N-1){auto [a,b] = A[i] ;C << a << KU << b << E}}void debag_Edge(V<Edge> A){ll N = A.size() ;rep(i,0,N-1){auto [a,b,c] = A[i] ;C << a << KU << b << KU << c << E}}/*st Regex(st S, st A ,st B){return regex_replace(S,regex(A),B) ;}st erase_string(st S , st T){st ans = S.erase(S.find(T),T.length()) ;return ans ;}*/ll pow_daisyou(ll a , ll b , ll c){ll d = c%2==1 ? 1 : 2 ;ll ans = -1 ;if(powpow(a,d) == powpow(b,d))ans = 0 ;if(powpow(a,d) > powpow(b,d))ans = 1 ;else if(powpow(a,d) < powpow(b,d))ans = 2 ;return ans ;}template<class T> T pow_mod(T A, T N, T M) {T res = 1 % M;A %= M;while (N) {if (N & 1) res = (res * A) % M;A = (A * A) % M;N >>= 1;}return res;}// Miller-Rabin 素数判定bool nis(ll N) {if (N <= 1) return false;if (N == 2) return true;if (N == 3) return true ;if (N == 5) return true ;if (N == 7) return true ;if (N == 11) return true ;if (N % 2 == 0 || N % 3 == 0 || N % 5 == 0 || N % 7 == 0 || N % 11 == 0 ) return false ;vector<ll> A = {2, 325, 9375, 28178, 450775,9780504, 1795265022};ll s = 0, d = N - 1;while (d % 2 == 0) {++s;d >>= 1;}fore(a,A) {if (a % N == 0) return true;ll t, x = pow_mod<__int128_t>(a, d, N);if (x != 1) {for (t = 0; t < s; ++t) {if (x == N - 1) break;x = __int128_t(x) * x % N;}if (t == s) return false;}}return true;}// UF.initはいっかいだけならいいけど、二回目以降はrepで初期化vector<ll> par;class UnionFind {public:// サイズをGET!void init(ll sz) {par.resize(sz,-1);}// 各連結成分の一番上を返すll root(ll x) {if (par[x] < 0) return x;return par[x] = root(par[x]);}// 結合作業bool unite(ll x, ll y) {x = root(x); y = root(y);if (x == y) return false;if (par[x] > par[y]) swap(x,y);par[x] += par[y];par[y] = x;return true;}// 同じグループか判定bool same(ll x, ll y) { return root(x) == root(y);}// グループのサイズをGET!ll size(ll x) { return -par[root(x)];}};UnionFind UF ;vector<ll> enumdiv(ll n) {vector<ll> S;for (ll i = 1; i*i <= n; i++) if (n%i == 0) { S.pb(i); if (i*i != n) S.pb(n / i); }sort(S.begin(), S.end());return S;}template<typename T> using min_priority_queue = priority_queue<T, vector<T>, greater<T>>;template<typename T> using max_priority_queue = priority_queue<T, vector<T>, less<T>> ;// 使用例 min_priority_queue<ll (ここは型)> Q ;template<typename T> using max_multiset = multiset<T, greater<T>>;vector<pair<long long, long long>> prime_factorize(long long N){vector<pair<long long, long long>> res;for(long long a = 2; a * a <= N; ++a){if(N % a != 0) continue;long long ex = 0;while(N % a == 0) ++ex, N /= a;res.push_back({a,ex});}if(N != 1) res.push_back({N,1});return res;}ll binpower(ll a, ll b,ll c) {if(!b) return 1 ;a %= c ;ll d = binpower(a,b/2,c) ;(d *= d) %= c ;if(b%2) (d *= a) %= c ;return d ;}map<ll,ll> Compression(V<ll> A){sort(all(A)) ;A.erase(unique(all(A)),A.end()) ;map<ll,ll> res ;ll index = 0 ;fore(u,A){res[u] = index ;index ++ ;}return res ;}struct sqrt_machine{V<ll> A ;const ll M = 1000000 ;bool p = false ;void init(){p = true ;A.pb(-1) ;rep(i,1,M){A.pb(i*i) ;}A.pb(LINF) ;}bool scan(ll a){if(p == false)init() ;ll pos = lower_bound(all(A),a) - A.begin() ;if(A[pos] == -1 || A[pos] == LINF || A[pos] != a)return false ;return true ;}};sqrt_machine SM ;ll a_b(V<ll> A,ll a,ll b){ll res = 0 ;res += upper_bound(all(A),b) - lower_bound(all(A),a) ;return res ;}struct era{ll check[10000010] ;bool p = false ;void init(){p = true ;rep(i,2,10000000){if(check[i] == 0){for(ll j = i + i ;j <= 10000000 ; j += i){check[j] ++ ;}}}}bool look(ll x){if(p == false)init() ;if(x == 1)return false ;if(check[x] == 0)return true ;else return false ;}ll enu_count(ll x){if(p == false)init() ;if(x == 1)return 1 ;if(check[x] == 0)return 1 ;return check[x] ;}};era era ;V<tuple<char,ll,ll,ll>> Run_Length_Encoding(st S){ll N = S.size() ;V<tuple<char,ll,ll,ll>> A ;ll count = 0 ;char cc ;bool RLEflag = false ;ll l = 0 ;ll r = 0 ;if(N == 1){A.pb({S[0],1,0,0}) ;RLEflag = true ;}rep(i,0,N-1){if(RLEflag == true)break ;if(i == 0){cc = S[i] ;count = 1 ;l = 0 ;r = 0 ;continue ;}r ++ ;if(i == N-1){if(S[i] == cc){A.pb({cc,count + 1,l,N-1}) ;}else{A.pb({cc,count,l,N-2}) ;A.pb({S[i],1,N-1,N-1}) ;}break ;}if(S[i] == cc){count ++ ;}else{A.pb({cc,count,l,r-1}) ;cc = S[i] ;count = 1 ;l = i ;r = i ;}}return A ;}V<tuple<ll,ll,ll,ll>> Run_Length_Encoding_Vector(V<ll> A){ll N = A.size() ;V<tuple<ll,ll,ll,ll>> res ;ll count = 0 ;ll cc = 0 ;bool RLEflag = false ;ll l = 0 ;ll r = 0 ;if(N == 1){res.pb({A[0],1,0,0}) ;RLEflag = true ;}rep(i,0,N-1){if(RLEflag == true)break ;if(i == 0){cc = A[i] ;count = 1 ;l = 0 ;r = 0 ;continue ;}r ++ ;if(i == N-1){if(A[i] == cc){res.pb({cc,count+1,l,N-1}) ;}else{res.pb({cc,count,l,N-2}) ;res.pb({A[i],1,N-1,N-1}) ;}break ;}if(A[i] == cc){count ++ ;}else{res.pb({cc,count,l,r-1}) ;cc = A[i] ;count = 1 ;l = i ;r = i ;}}return res ;}bool Palindrome_Judgement(st S){ll l = 0 ;ll r = S.size() - 1 ;bool flag = true ;while(1){if(S[l] != S[r])flag = false ;l ++ ;r -- ;if(r < l)break ;}return flag ;}// n => 10long long _n_to_10(string N,ll n) {long long res = 0;for (int i = 0; i < (int)N.size(); ++i) {res = res * n + int(N[i] - '0');}return res;}// 10 => nstring _10_to_n(long long N,ll n) {if (N == 0) {return "0";}string res;while (N > 0) {res = char(N % n + '0') + res;N /= n;}return res;}/*2次元BIT(閉区間)Nyannさんの https://nyaannyaan.github.io/library/data-structure-2d/2d-binary-indexed-tree.hpp問題 https://mojacoder.app/en/users/shinnshinn/contests/ochacon01/tasks/6提出 https://mojacoder.app/en/users/shinnshinn/contests/ochacon01/submissions/8cea7bfd-0e5b-4574-8542-77c07121e72c機能初期化 BinaryIndexedTree2D<T(型)> bit(H,W) H*Wの2次元配列を宣言bit(3,3)なら3,3にもアクセスできる点加算 bit.add(x,y,w) 点(x,y)にwを加算領域和 bit.sum(x1,y1,x2,y2) 点(x1,y1) から 点(x2,y2) の領域の和を求める [l,r]なことに注意点取得 bit.get(x,y) 点(x,y)の値を取得*/template <typename T>struct BinaryIndexedTree2D {ll H, W;vector<vector<T>> bit;BinaryIndexedTree2D(ll _H, ll _W) : H(_H + 1), W(_W + 1) {bit.resize(H + 3, vector<T>(W + 3, 0));}// 関数の入力のindexは0-originを想定// (x,y)にwを足す// 範囲外の時は足さないvoid add(ll x, ll y, T w) {if (x < 0 || x >= H || y < 0 || y >= W) return;for (ll a = (++y, ++x); a <= H; a += a & -a) {for (ll b = y; b <= W; b += b & -b) {bit[a][b] += w;}}}// imos法で[(x1,y1) , (x2,y2)]にwを足すvoid imos(ll x1, ll y1, ll x2, ll y2, T w) {add(x1, y1, w);add(x1, y2 + 1, -w);add(x2 + 1, y1, -w);add(x2 + 1, y2 + 1, w);}// [(0,0) , (x,y)]の和 閉区間に注意!// x,y<0の時は0 x>=H y>=Wのときはx=H-1,y=W-1とみなす// ( imos法の時は (x,y)の値を返す )T sum(ll x, ll y) {if (x < 0 || y < 0) return 0;if (x >= H) x = H - 1;if (y >= W) y = W - 1;T ret = 0;for (ll a = (++y, ++x); a > 0; a -= a & -a) {for (ll b = y; b > 0; b -= b & -b) {ret += bit[a][b];}}return ret;}// [(x1,y1) , (x2,y2)] の和// x1 > x2, y1 > y2の時はswapT sum(ll x1, ll y1, ll x2, ll y2) {if (x1 > x2 || y1 > y2) return T(0);return sum(x2, y2) - sum(x2, y1 - 1) - sum(x1 - 1, y2) +sum(x1 - 1, y1 - 1);}T get(ll x, ll y){return sum(x,y,x,y) ;}};template<typename T>V<T> two_to_one(VV<T> A){V<T> res ;ll n = A.size() ;ll m = A[0].size() ;rep(i,0,n-1)rep(j,0,m-1){res.pb(A[i][j]) ;}return res ;}template<typename T>VV<T> one_to_two(V<T> A , ll N , ll M){VV<T> res(N,V<T>(M)) ;ll index = 0 ;rep(i,0,N-1)rep(j,0,M-1){res[i][j] = A[index] ;index ++ ;}return res ;}/*座圧imos法問題 https://atcoder.jp/contests/abc309/tasks/abc309_c提出 https://atcoder.jp/contests/abc309/submissions/43446308問題 https://atcoder.jp/contests/abc221/tasks/abc221_d提出 https://atcoder.jp/contests/abc221/submissions/43446643問題 https://atcoder.jp/contests/abc294/submissions/43448272提出 https://atcoder.jp/contests/abc294/tasks/abc294_e問題 https://atcoder.jp/contests/abc312/tasks/abc312_c提出 https://atcoder.jp/contests/abc312/submissions/44156572 区間の加算を工夫したやつ機能imos.init(V<Edge> A) : 初期化imos.array() : 下みたいに返す [a,b]imos.day_information(ll x ) : x日の値返す O(logN)imos.Section_array() : imosした後区間の状況を返す [a,b,c] みたいにimos.reset() : 全部空にする区間[a,b] に +cしたい!をN個与えていい感じに処理する。したあとの配列を <day,x> で返すex)[1,2] +3[2,3] +4 なら1 32 73 44 01000000000000000002 0で返す (LINFは一応)*/struct imos{V<Edge> number ;map<ll,ll> MAP ;map<ll,ll> MMAP ;V<ll> Imos ;V<ll> search ;imos(V<Edge> A) {ll N = A.size() ;number.resize(N+1) ;rep(i,0,N-1){auto [a,b,c] = A[i] ;number[i] = {a,b+1,c} ;}number[N] = {LINF,LINF,0} ;V<ll> x ;rep(i,0,N){auto [a,b,c] = number[i] ;x.pb(a) ;x.pb(b) ;}MAP = Compression(sort_erase_unique(x)) ;ll M = MAP.size() ;Imos.resize(M+1) ;rep(i,0,N){auto [a,b,c] = number[i] ;ll aa = MAP[a] ;ll bb = MAP[b] ;MMAP[aa] = a ;MMAP[bb] = b ;Imos[aa] += c ;Imos[bb] -= c ;}rep(i,0,M-1){Imos[i+1] += Imos[i] ;}fore(u,MAP){auto [a,b] = u ;search.pb(a) ;}}void reset(){number.clear() ;Imos.clear() ;search.clear() ;MAP.clear() ;MMAP.clear() ;}V<P> array(){ll M = Imos.size() ;V<P> res(M-1) ;rep(i,0,M-2){res[i] = {MMAP[i],Imos[i]} ;}res.ppb() ;return res ;}V<Edge> Section_array(){ll M = Imos.size() ;V<Edge> res ;rep(i,0,M-2){res.pb({MMAP[i],MMAP[i+1]-1,Imos[i]}) ;}res.ppb() ;return res ;}ll day_information(ll k){ll p = search[0] ;if(k < p)return 0 ;ll index = upper_bound(all(search),k) - search.begin() ;index -- ;ll day = search[index] ;ll res = MAP[day] ;return Imos[res] ;}};/*配列の二分探索をするやつ初期化はO(NlogN)それ以外は,O(logN)nibutan.init(V<ll> A) 初期化nibutan.greater_than_equal(ll x) 以上nibutan.greater_than(ll x) 超えるnibutan.less_than_equal(ll x) 以下nibutan.less_than(ll x) 未満nibutan.range_count(ll a , ll b) [a,b]の個数問題 https://atcoder.jp/contests/abc326/tasks/abc326_c提出 https://atcoder.jp/contests/abc326/submissions/47809268問題 https://atcoder.jp/contests/abc119/tasks/abc119_d提出 https://atcoder.jp/contests/abc119/submissions/47851167*/struct nibutan{V<ll> search ;nibutan(V<ll> A){search = A ;search.pb(LINF) ;search.pb(-LINF) ;sort(all(search)) ;}ll greater_than_equal(ll x){ll res = lower_bound(all(search),x) - search.begin() ;return search[res] ;}ll greater_than(ll x){ll res = upper_bound(all(search),x) - search.begin() ;return search[res] ;}ll less_than_equal(ll x){ll res = upper_bound(all(search),x) - search.begin() - 1 ;return search[res] ;}ll less_than(ll x){ll res = lower_bound(all(search),x) - search.begin() - 1 ;return search[res] ;}ll range_count(ll a , ll b){if(a > b)swap(a,b) ;ll left = lower_bound(all(search),a) - search.begin() ;ll right = upper_bound(all(search),b) - search.begin() - 1;return right - left + 1 ;}};template<typename T>V<V<T>> A_NM_twice(V<V<T>> A,ll a , ll b){// 0はだめassert(a != 0);assert(b != 0);ll N = A.size() ;ll M = A[0].size() ;ll new_N = N * a ;ll new_M = M * b ;V<V<T>> new_A(new_N,V<T>(new_M)) ;rep(i,0,new_N-1){rep(j,0,new_M-1){new_A[i][j] = A[i%N][j%M] ;}}return new_A ;}bool bingo_game(VV<bool> A){bool flag = false ;ll N = A.size() ;ll M = A[0].size() ;// 横一列rep(i,0,N-1){bool fflag = true ;rep(j,0,M-1){fflag &= A[i][j] ;}if(fflag)flag = true ;}// 縦一列rep(i,0,M-1){bool fflag = true ;rep(j,0,N-1){fflag &= A[j][i] ;}if(fflag)flag = true ;}// 斜め1bool fflag = true ;rep(i,0,N-1){fflag &= A[i][i] ;}if(fflag)flag = true ;// 斜め2bool ffflag = true ;rep(i,0,N-1){ffflag &= A[i][N-1-i] ;}return flag ;}/*初期化 BiCoef<mint> bc(N) ;mod0かmod1か選ぶ出来ることi! ====> bc.fact(i) ;(1/i!) ====> bc.finv(i) ;bc.com(n,k) ====> bc.com(n,k) ;1/i ====> bc.inv(i) ;*/// modinttemplate<int MOD> struct Fp {long long val;constexpr Fp(long long v = 0) noexcept : val(v % MOD) {if (val < 0) val += MOD;}constexpr int getmod() const { return MOD; }constexpr Fp operator - () const noexcept {return val ? MOD - val : 0;}constexpr Fp operator + (const Fp& r) const noexcept { return Fp(*this) += r; }constexpr Fp operator - (const Fp& r) const noexcept { return Fp(*this) -= r; }constexpr Fp operator * (const Fp& r) const noexcept { return Fp(*this) *= r; }constexpr Fp operator / (const Fp& r) const noexcept { return Fp(*this) /= r; }constexpr Fp& operator += (const Fp& r) noexcept {val += r.val;if (val >= MOD) val -= MOD;return *this;}constexpr Fp& operator -= (const Fp& r) noexcept {val -= r.val;if (val < 0) val += MOD;return *this;}constexpr Fp& operator *= (const Fp& r) noexcept {val = val * r.val % MOD;return *this;}constexpr Fp& operator /= (const Fp& r) noexcept {long long a = r.val, b = MOD, u = 1, v = 0;while (b) {long long t = a / b;a -= t * b, swap(a, b);u -= t * v, swap(u, v);}val = val * u % MOD;if (val < 0) val += MOD;return *this;}constexpr bool operator == (const Fp& r) const noexcept {return this->val == r.val;}constexpr bool operator != (const Fp& r) const noexcept {return this->val != r.val;}friend constexpr istream& operator >> (istream& is, Fp<MOD>& x) noexcept {is >> x.val;x.val %= MOD;if (x.val < 0) x.val += MOD;return is;}friend constexpr ostream& operator << (ostream& os, const Fp<MOD>& x) noexcept {return os << x.val;}friend constexpr Fp<MOD> modpow(const Fp<MOD>& r, long long n) noexcept {if (n == 0) return 1;if (n < 0) return modpow(modinv(r), -n);auto t = modpow(r, n / 2);t = t * t;if (n & 1) t = t * r;return t;}friend constexpr Fp<MOD> modinv(const Fp<MOD>& r) noexcept {long long a = r.val, b = MOD, u = 1, v = 0;while (b) {long long t = a / b;a -= t * b, swap(a, b);u -= t * v, swap(u, v);}return Fp<MOD>(u);}};// Binomial coefficienttemplate<class T> struct BiCoef {vector<T> fact_, inv_, finv_;constexpr BiCoef() {}constexpr BiCoef(int n) noexcept : fact_(n, 1), inv_(n, 1), finv_(n, 1) {init(n);}constexpr void init(int n) noexcept {fact_.assign(n, 1), inv_.assign(n, 1), finv_.assign(n, 1);int MOD = fact_[0].getmod();for(int i = 2; i < n; i++){fact_[i] = fact_[i-1] * i;inv_[i] = -inv_[MOD%i] * (MOD/i);finv_[i] = finv_[i-1] * inv_[i];}}constexpr T com(int n, int k) const noexcept {if (n < k || n < 0 || k < 0) return 0;return fact_[n] * finv_[k] * finv_[n-k];}constexpr T fact(int n) const noexcept {if (n < 0) return 0;return fact_[n];}constexpr T inv(int n) const noexcept {if (n < 0) return 0;return inv_[n];}constexpr T finv(int n) const noexcept {if (n < 0) return 0;return finv_[n];}};// const int MOD = mod0 ;const int MOD = mod1 ;using mint = Fp<MOD> ;int main(void){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);//------------ちょっとした省略系---------------// -----------数列-----------------------------// max_element(V<ll> A) Aの最大値を返す// max_element_index(V<ll> A) Aの最大値のindex// min_element(V<ll> A) Aの最小値を返す// min_element_index(V<ll> A) Aの最小値のindex// array_sub(V<ll> A , ll l , ll r) 配列でやる// V<V<ll>> Vector_Next_Permutation配列Aでやる// sort_erase_unique(V<ll> A) sortしてeraseしてuniqueする関数// sr(V<ll> A) 配列を入れたら、sort --→ reverse して返してくれる関数 受け取りは auto とかで// sum_V , sum_D , sum_Q vector , deque , queue の和を返す関数// shift_right(V<T> A, ll k) 数列を右にk個shiftする// shift_left(V<T> A , ll k) 数列を左にk個shiftする// one_to_two(V<T> A , ll n , ll m) n×mの二次元配列にする// two_to_one(VV<T> A) 二次元配列を1次元配列にする// -----------数列-----------------------------// -----------文字列---------------------------// is_lower_and_upper(char c) 小文字、大文字なんでも変換 小文字 = 1 , 大文字 = 2 pair型// V<st> String_Next_Permutation(st N) stringでnext_permutation// Sub(st S,ll l , ll r) 文字列Sのl文字目からr文字目// reading_x(st s , ll size , ll x , ll lr) 文字列sをsizeになるまで、数字xで右(0)か左(1)で埋める// -----------文字列---------------------------// -----------数字-----------------------------// gcd(ll a , ll b) gcd(a,b) ;// lcm(ll a ,ll b ) lcm// k_lcm k個のlcm返す関数 空なら 1 、0なら0 、 overflowなら-1// k_gcd(V<ll> A) k個のgcd返す関数// Random_Number(ll a , ll b) [a,b]からランダムな数を返す関数 2*10^5 回やると大体1secぐらい// powpow(ll a,ll b) a^b を返す// Permutation(ll N) N!の値を返す。20までならオーバーフローしない。// Arithmetic_Sequence(ll l , ll r) [l,r]の等差数列の和// Ceil(x,y) 小数点以下切り上げ// Floor(x,y) 切り捨て// range_multiple_count(l,r,x) 区間[l,r]のxの倍数を数える// Crossing_Section(P A , P B) 二つの閉区間が共通部分をもつかどうか// -----------数字-----------------------------//-----------debag系---------------------------// debag_1V_kaigyou(V<ll> A) 一次元配列の中身を改行区切りで出力する// debag_1V_space(V<ll> A) 一次元配列Aの中身をspace区切りで出力する// debag_2V(V<V<ll>> A) 2次元配列Aの中身を返す関数// debag_2V_other(V<V<T>> A) 2次元配列Aの中身を返す関数// debag_pair(V<P> A) pair型配列の中身を出力する// debag_Edge(V<Edge> A) Edge型配列の中身を出力する//-----------debag系---------------------------// ---------いつ使うの?-----------------------// Regex(st S, st A , st B) SのAをBに変えた文字列を返す 使う場合は消す// erase_string(st S , st T) Sの中のTを消す// pow_daisyou(ll a, ll b , ll c )a^cとb^cを比較する 0 => 同値 1 => a側 2=> b側// ---------いつ使うの?-----------------------//------------アルゴリズム系-------------------// nis(ll a) 素数判定 素数ならtrue// UF UF.init(ll N) ; UF.root(i) ; UF.unite(a,b) ; UF.same(a,b) ; UF.size(i) ;// enumdiv(ll a ) 約数列挙// binpower(a,b,c) aのb条 をcでわったやつをO(logb) でだしてくれるやつ// Compression(V<ll> A) 座圧したmapを返す関数// SM.scan(ll a) で 平方数ならtrue が返ってくる。 範囲は √10^6まで SM.init() 必ず起動する。// era.look(ll a) --→ true 素数 / era.enu_count(ll a) --→ 素因数の個数 1は1 、素数も1 その他はそのまんま 範囲は10^7まで// Run_Length_Encoding(st S) ランレングス圧縮して配列を返す tuple<char,ll,ll,ll> (S[i],length,l,r)// Run_Length_Encoding_Vector(V<ll> A) 数列版のRLE tuple<ll,ll,ll,ll>// prime_factorize(ll p) aのb乗のかたちででてくる 配列で受け取る// Palindrome_Judgement(st S) 回分判定// _10_to_n(ll a , ll n) 10進数をn進数に直す (n <= 9) ll => st// _n_to_10(st S,ll n) n進数を10進数に直す (n <= 9) st => ll// BinaryIndexedTree2D 二次元BIT 831行目見て BinaryIndexedTree2D<ll> bit(H,W) ;// imos法 959行目見て 初期化はこう宣言する imos A(V<Edge> B)// nibutan 1073行目見て nibutan B(A) ;//------------アルゴリズム系-------------------//---------------------------------------------// A_NM_twice(A,N,M) 配列を 縦にN 横にM倍する// bingo_game(A) 二次元配列のビンゴを判定する// (double)clock()/CLOCKS_PER_SEC>1.987// mod0 --→ 1000000007 mod1 --→ 998244353 最初はmod1になってるので、注意// S.substr(i,k) = [i,i+k) = [i,i+k-1]// A~Z 65~90 a~z 97~122 V<char> には'\0'が初期値// VV<ll> dp(N+1,V<ll>(N+1,LINF)) ;// VVV<ll> dp(N+1,VV<ll>(2,V<ll>(2,LINF))) ;// n ==> 10 stoll(S,nullptr,n)// 10^18 < 2^60 , 3^38 , 5^26 , 7^22// 11! < 10^8 < 12!// 二次元でUFするとき i * W + j % W ;// 方向決めてその方向に伸ばし続けるやつ y = i + Y8[k] * p// 文字列の逆は S[l,r] = S[N-r,N-l] ;// ദ്ദിᐢ- ̫-ᐢ₎ll N ;cin >> N ;V<ll> A(N) ;rep(i,0,N-1){cin >> A[i] ;}sort(all(A)) ;mint x = 0 ;rep(i,0,N-1){x = mint(10LL) * x + A[i] ;}C << x << E// if(dx < 0 || dy < 0 || dx >= W || dy >= H) continue ;// C << fixed << setprecision(10) << // 勝手に四捨五入してくれてるから安心して// sqrt( (c - a)*(c - a) + (d - b)*(d - b) ) ;re}