#ifndef HIDDEN_IN_VS // 折りたたみ用 // 警告の抑制 #define _CRT_SECURE_NO_WARNINGS // ライブラリの読み込み #include using namespace std; // 型名の短縮 using ll = long long; using ull = unsigned long long; // -2^63 ~ 2^63 = 9 * 10^18(int は -2^31 ~ 2^31 = 2 * 10^9) using pii = pair; using pll = pair; using pil = pair; using pli = pair; using vi = vector; using vvi = vector; using vvvi = vector; using vvvvi = vector; using vl = vector; using vvl = vector; using vvvl = vector; using vvvvl = vector; using vb = vector; using vvb = vector; using vvvb = vector; using vc = vector; using vvc = vector; using vvvc = vector; using vd = vector; using vvd = vector; using vvvd = vector; template using priority_queue_rev = priority_queue, greater>; using Graph = vvi; // 定数の定義 const double PI = acos(-1); int DX[4] = {1, 0, -1, 0}; // 4 近傍(下,右,上,左) int DY[4] = {0, 1, 0, -1}; int INF = 1001001001; ll INFL = 4004004003094073385LL; // (int)INFL = INF, (int)(-INFL) = -INF; // 入出力高速化 struct fast_io { fast_io() { cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(18); } } fastIOtmp; // 汎用マクロの定義 #define all(a) (a).begin(), (a).end() #define sz(x) ((int)(x).size()) #define lbpos(a, x) (int)distance((a).begin(), std::lower_bound(all(a), x)) #define ubpos(a, x) (int)distance((a).begin(), std::upper_bound(all(a), x)) #define Yes(b) {cout << ((b) ? "Yes\n" : "No\n");} #define rep(i, n) for(int i = 0, i##_len = int(n); i < i##_len; ++i) // 0 から n-1 まで昇順 #define repi(i, s, t) for(int i = int(s), i##_end = int(t); i <= i##_end; ++i) // s から t まで昇順 #define repir(i, s, t) for(int i = int(s), i##_end = int(t); i >= i##_end; --i) // s から t まで降順 #define repe(v, a) for(const auto& v : (a)) // a の全要素(変更不可能) #define repea(v, a) for(auto& v : (a)) // a の全要素(変更可能) #define repb(set, d) for(int set = 0, set##_ub = 1 << int(d); set < set##_ub; ++set) // d ビット全探索(昇順) #define repis(i, set) for(int i = lsb(set), bset##i = set; i >= 0; bset##i -= 1 << i, i = lsb(bset##i)) // set の全要素(昇順) #define repp(a) sort(all(a)); for(bool a##_perm = true; a##_perm; a##_perm = next_permutation(all(a))) // a の順列全て(昇順) #define uniq(a) {sort(all(a)); (a).erase(unique(all(a)), (a).end());} // 重複除去 #define EXIT(a) {cout << (a) << endl; exit(0);} // 強制終了 #define inQ(x, y, u, l, d, r) ((u) <= (x) && (l) <= (y) && (x) < (d) && (y) < (r)) // 半開矩形内判定 // 汎用関数の定義 template inline ll powi(T n, int k) { ll v = 1; rep(i, k) v *= n; return v; } template inline bool chmax(T& M, const T& x) { if (M < x) { M = x; return true; } return false; } // 最大値を更新(更新されたら true を返す) template inline bool chmin(T& m, const T& x) { if (m > x) { m = x; return true; } return false; } // 最小値を更新(更新されたら true を返す) template inline T getb(T set, int i) { return (set >> i) & T(1); } template inline T smod(T n, T m) { n %= m; if (n < 0) n += m; return n; } // 非負mod // 演算子オーバーロード template inline istream& operator>>(istream& is, pair& p) { is >> p.first >> p.second; return is; } template inline istream& operator>>(istream& is, vector& v) { repea(x, v) is >> x; return is; } template inline vector& operator--(vector& v) { repea(x, v) --x; return v; } template inline vector& operator++(vector& v) { repea(x, v) ++x; return v; } #endif // 折りたたみ用 #if __has_include() #include using namespace atcoder; #ifdef _MSC_VER #include "localACL.hpp" #endif //using mint = modint1000000007; using mint = modint998244353; //using mint = modint; // mint::set_mod(m); namespace atcoder { inline istream& operator>>(istream& is, mint& x) { ll x_; is >> x_; x = x_; return is; } inline ostream& operator<<(ostream& os, const mint& x) { os << x.val(); return os; } } using vm = vector; using vvm = vector; using vvvm = vector; using vvvvm = vector; using pim = pair; #endif #ifdef _MSC_VER // 手元環境(Visual Studio) #include "local.hpp" #else // 提出用(gcc) inline int popcount(int n) { return __builtin_popcount(n); } inline int popcount(ll n) { return __builtin_popcountll(n); } inline int lsb(int n) { return n != 0 ? __builtin_ctz(n) : -1; } inline int lsb(ll n) { return n != 0 ? __builtin_ctzll(n) : -1; } template inline int lsb(const bitset& b) { return b._Find_first(); } inline int msb(int n) { return n != 0 ? (31 - __builtin_clz(n)) : -1; } inline int msb(ll n) { return n != 0 ? (63 - __builtin_clzll(n)) : -1; } #define dump(...) #define dumpel(v) #define dump_list(v) #define dump_mat(v) #define input_from_file(f) #define output_to_file(f) #define Assert(b) { if (!(b)) { vc MLE(1<<30); EXIT(MLE.back()); } } // RE の代わりに MLE を出す #endif //【static top tree】(の改変) /* * Static_top_tree(Graph g, int r) : O(n (log n)^2) * r を根とする根付き木 g で初期化する. * * set(int s) : O((log n)^2) * 頂点 s の情報の更新を反映する. * * S get() : O(1) * 根付き木全体の値を返す. * * なおテンプレート引数が表す関数は以下の通りとする: * * S get_val(int s) : * 葉 s のみからなる部分木についての値を返す. * * F get_fnc(int s) : * 節点 s のみからなる欠損部分木(子が 1 つ欠けた部分木)について, * 関数 : (欠けた部分木の値 → 部分木 s の値) を返す. * * S add_edge(S x, int s) : * 部分木 s の値が x でその親が p のとき, * 辺 p'→s を追加した開部分木 p' についての答えを返す(記号 ' は開頂点を表す) * * S merge(S x, S y) : * 開根を共有する開部分木 2 つの値がそれぞれ x, y のとき,それらをマージした開部分木の値を返す. * * F add_vtx(S x, int s) : * 開根 s' をもつ開部分木 s' の値が x のとき, * 根 s を追加した欠損部分木 s についての関数 : (欠けた部分木の値 → 部分木 s の値) を返す. * * F comp(F f, F g) : * 合成関数 f o g を返す. * * S act(F f, S x) : * f(x) を返す. */ template class Static_top_tree { // 参考 : https://atcoder.jp/contests/abc351/editorial/9868 struct Node { // tp : ノードのタイプ // A:act, C:comp, V:add_vtx, M:merge, E:add_edge, f:get_fnc, x:get_val char tp = '?'; // id : heavy path ならその根,light child ならその親 // ただし二分木の構築後は不要になるので,使い回して参照すべき頂点番号を表す. int id = -1; // [l..r) : heavy path, light child 共にどの範囲を見ているか int l = -1, r = -1; // pp : 親ノードへのポインタ,lp[rp] : 左[右]の子ノードへのポインタ // ただし子が 1 つの場合は lp のみを使用する. Node* pp = nullptr, * lp = nullptr, * rp = nullptr; // f : 関数 F f; // x : 値 S x; }; // root : 根(根付き木全体に対応する) Node* root; // st[s] : 頂点 s の変更があったとき,どのノードから更新を始めればいいか vector st; public: // r を根とする根付き木 g で初期化する. Static_top_tree(const Graph& g, int rt) { // verify : https://atcoder.jp/contests/abc351/tasks/abc351_g int n = sz(g); // j_max[s] : s の重さ最大の部分木が何番目か vi j_max(n, -1); // 部分木の重さを調べる. function dfs_wgt = [&](int s, int p) { int ws = 0; int wt_max = -INF; rep(j, sz(g[s])) { auto t = g[s][j]; if (t == p) continue; int wt = dfs_wgt(t, s); ws += wt + 1; if (chmax(wt_max, wt)) j_max[s] = j; } return ws; }; dfs_wgt(rt, -1); // hp[s] : 根を s とする heavy path を成す頂点の列(深さ降順) vvi hp(n); // lc[s] : 頂点 s の light child のリスト vvi lc(n); // HL 分解を行う. function dfs_hld = [&](int s, int p, int r) { hp[r].push_back(s); if (j_max[s] != -1) { int t = g[s][j_max[s]]; dfs_hld(t, s, r); } rep(j, sz(g[s])) { int t = g[s][j]; if (t == p || j == j_max[s]) continue; lc[s].push_back(t); dfs_hld(t, s, t); } }; dfs_hld(rt, -1, rt); root = new Node{ 'A', rt, 0, sz(hp[rt]) }; st.resize(n); // トップダウンに二分木を構築する. function dfs_btree = [&](Node* p) { if (p->tp == 'A' || p->tp == 'C') { if (p->r - p->l > 1) { int m = (p->l + p->r) / 2; p->lp = new Node{ 'C', p->id, p->l, m, p }; dfs_btree(p->lp); p->rp = new Node{ p->tp, p->id, m, p->r, p }; dfs_btree(p->rp); if (p->tp == 'A') p->x = act(p->lp->f, p->rp->x); else p->f = comp(p->lp->f, p->rp->f); } else { p->id = hp[p->id][p->l]; // 使い回して頂点番号を入れておく st[p->id] = p; int r = sz(lc[p->id]); if (r > 0) { p->tp = 'V'; p->lp = new Node{ 'M', p->id, 0, r, p }; dfs_btree(p->lp); p->f = add_vtx(p->lp->x, p->id, p->lp->id); } else { if (p->tp == 'A') { p->tp = 'x'; p->x = get_val(p->id); } else { p->tp = 'f'; p->f = get_fnc(p->id); } } } } else if (p->tp == 'M') { if (p->r - p->l > 1) { int m = (p->l + p->r) / 2; p->lp = new Node{ 'M', p->id, p->l, m, p }; dfs_btree(p->lp); p->rp = new Node{ 'M', p->id, m, p->r, p }; dfs_btree(p->rp); p->x = merge(p->lp->x, p->rp->x); } else { p->id = lc[p->id][p->l]; // 使い回して頂点番号を入れておく int r = sz(hp[p->id]); p->tp = 'E'; p->lp = new Node{ 'A', p->id, 0, r, p }; dfs_btree(p->lp); p->x = add_edge(p->lp->x, p->id); } } }; dfs_btree(root); } // 根付き木全体の値を返す. S get() { // verify : https://atcoder.jp/contests/abc351/tasks/abc351_g return root->x; } /* 雛形 using S = mint; struct F { mint a, b; }; S get_val(int v) { return a[v]; } F get_fnc(int v) { return { 1, a[v] }; } S add_edge(const S& x, int i) { return x; } S merge(const S& x, const S& y) { return x * y; } F add_vtx(const S& x, int v) { return { x, a[v] }; } F comp(const F& f, const F& g) { return { f.a * g.a, f.a * g.b + f.b }; } S act(const F& f, const S& x) { return f.a * x + f.b; } Static_top_tree G(g, 0); */ }; #include using Bint = boost::multiprecision::cpp_int; string to_string(boost::multiprecision::cpp_int x, int B = 10) { using Bint = boost::multiprecision::cpp_int; if (x == 0) return "0"; bool neg = false; if (x < 0) { x *= -1; neg = true; } // powB[k] : B^(2^k) vector powB{ B }; while (powB.back() < x) powB.push_back(powB.back() * powB.back()); powB.pop_back(); int K = sz(powB), n = 1 << K; dump(K); dump(powB); // a : 完全二分木(左の子は商,右の子は余りをとった値をもつ) vector a(2 * n); a[1] = x; repi(i, 1, n - 1) { int k = K - 1 - msb(i); a[2 * i + 0] = a[i] / powB[k]; a[2 * i + 1] = a[i] % powB[k]; } dumpel(a); string s; bool l0 = true; if (neg) s += '-'; repi(i, n, 2 * n - 1) { if (l0 && a[i] == 0) continue; l0 = false; s += a[i].str(); } dump(s); return s; } string s; int i; vi l, r; vc op; vector v; int pt = 0; int number2() { int sgn = 1; while (s[i] == '-') { i++; sgn *= -1; } string num; while (isdigit(s[i])) { num += s[i]; i++; } l.push_back(-1); r.push_back(-1); op.push_back('n'); v.emplace_back(sgn * Bint(move(num))); // TLE return pt++; } int expression2(); int factor2() { int x = -1; if (s[i] == '(') { i++; x = expression2(); i++; } else { x = number2(); } return x; } int term2() { int x = factor2(); while (1) { if (s[i] == '*') { i++; int y = factor2(); l.push_back(x); r.push_back(y); op.push_back('*'); v.emplace_back(0); x = pt++; } else break; } return x; } int expression2() { int x = term2(); while (1) { if (s[i] == '+') { i++; int y = term2(); l.push_back(x); r.push_back(y); op.push_back('+'); v.emplace_back(0); x = pt++; } else if (s[i] == '-') { i++; int y = term2(); l.push_back(x); r.push_back(y); op.push_back('-'); v.emplace_back(0); x = pt++; } else break; } return x; } vc lr; using S = Bint; struct F { Bint a, b; }; S get_val(int s) { return v[s]; } F get_fnc(int s) { return { -INFL, -INFL }; } S add_edge(const S& x, int i) { return x; } S merge(const S& x, const S& y) { return -INFL; } F add_vtx(const S& x, int s, int t) { // '-' が交換法則を満たさないので順序木といて扱う必要がある. // そのために static top tree の改変が必要になった. if (op[s] == '+') return { 1, x }; if (op[s] == '-') { if (lr[t] == 'L') return { -1, x }; if (lr[t] == 'R') return { 1, -x }; } if (op[s] == '*') return { x, 0 }; return { -INFL, -INFL }; } F comp(const F& f, const F& g) { return { f.a * g.a, f.a * g.b + f.b }; } S act(const F& f, const S& x) { return f.a * x + f.b; } int main() { // input_from_file("input.txt"); // output_to_file("output.txt"); // Bint x("-123456789"); to_string(x, 10); exit(0); int n; cin >> n >> s; s.push_back('$'); // 数式の木を構築する. int rt = expression2(); dump(l); dump(r); dump(op); dump(v); dump(rt); dump(pt); // static top tree 用に再構築 Graph g(pt); lr.assign(pt, '?'); rep(s, pt) { if (l[s] != -1) { lr[l[s]] = 'L'; g[s].push_back(l[s]); g[l[s]].push_back(s); } if (r[s] != -1) { lr[r[s]] = 'R'; g[s].push_back(r[s]); g[r[s]].push_back(s); } } dumpel(g); dump(lr); Static_top_tree G(g, rt); cout << to_string(G.get()) << endl; }