// ----- BIGINT ----- #include #include using namespace std; const int DIGIT = 6; const int BASE = 1000000; struct positive_bigint{ std::vector d; positive_bigint(){ } positive_bigint(long long X){ while (X > 0){ d.push_back(X % BASE); X /= BASE; } } positive_bigint(std::string S){ if (S == "0"){ S = ""; } int L = S.size(); d.resize((L + DIGIT - 1) / DIGIT, 0); for (int i = L - 1; i >= 0; i -= 6){ for (int j = std::max(i - 5, 0); j <= i; j++){ d[i / DIGIT] *= 10; d[i / DIGIT] += S[j] - '0'; } } std::reverse(d.begin(), d.end()); } bool empty() const { return d.empty(); } int size() const { return d.size(); } int& operator [](int i){ return d[i]; } int operator [](int i) const { return d[i]; } }; std::string to_string(const positive_bigint &A){ int N = A.size(); std::string ans; for (int i = N - 1; i >= 0; i--){ std::string tmp = std::to_string(A[i]); if (i < N - 1){ ans += std::string(DIGIT - tmp.size(), '0'); } ans += tmp; } if (ans.empty()){ ans = "0"; } return ans; } std::istream& operator >>(std::istream &is, positive_bigint &A){ std::string S; is >> S; A = positive_bigint(S); return is; } std::ostream& operator <<(std::ostream &os, positive_bigint &A){ os << to_string(A); return os; } int cmp(const positive_bigint &A, const positive_bigint &B){ int N = A.size(); int M = B.size(); if (N < M){ return -1; } else if (N > M){ return 1; } else { for (int i = N - 1; i >= 0; i--){ if (A[i] < B[i]){ return -1; } if (A[i] > B[i]){ return 1; } } return 0; } } bool operator ==(const positive_bigint &A, const positive_bigint &B){ return cmp(A, B) == 0; } bool operator !=(const positive_bigint &A, const positive_bigint &B){ return cmp(A, B) != 0; } bool operator <(const positive_bigint &A, const positive_bigint &B){ return cmp(A, B) < 0; } bool operator >(const positive_bigint &A, const positive_bigint &B){ return cmp(A, B) > 0; } bool operator <=(const positive_bigint &A, const positive_bigint &B){ return cmp(A, B) <= 0; } bool operator >=(const positive_bigint &A, const positive_bigint &B){ return cmp(A, B) >= 0; } positive_bigint& operator +=(positive_bigint &A, const positive_bigint &B){ int N = A.size(); int M = B.size(); while (N < M){ A.d.push_back(0); N++; } for (int i = 0; i < M; i++){ A[i] += B[i]; } for (int i = 0; i < N - 1; i++){ if (A[i] >= BASE){ A[i] -= BASE; A[i + 1]++; } } if (N > 0){ if (A[N - 1] >= BASE){ A.d.push_back(1); A[N - 1] -= BASE; } } return A; } positive_bigint operator +(const positive_bigint &A, const positive_bigint &B){ positive_bigint A2 = A; A2 += B; return A2; } positive_bigint& operator -=(positive_bigint &A, const positive_bigint &B){ int N = A.size(); int M = B.size(); for (int i = 0; i < M; i++){ A[i] -= B[i]; } for (int i = 0; i < N - 1; i++){ if (A[i] < 0){ A[i] += BASE; A[i + 1]--; } } while (!A.empty()){ if (A.d.back() == 0){ A.d.pop_back(); } else { break; } } return A; } positive_bigint operator -(const positive_bigint &A, const positive_bigint &B){ positive_bigint A2 = A; A2 -= B; return A2; } positive_bigint operator *(const positive_bigint &A, const positive_bigint &B){ if (A.empty() || B.empty()){ return 0; } int N = A.size(); int M = B.size(); std::vector a(N); for (int i= 0; i < N; i++){ a[i] = A[i]; } std::vector b(M); for (int i = 0; i < M; i++){ b[i] = B[i]; } std::vector C = atcoder::convolution_ll(a, b); for (int i = 0; i < N + M - 2; i++){ C[i + 1] += C[i] / BASE; C[i] %= BASE; } if (C[N + M - 2] >= BASE){ C.resize(N + M); C[N + M - 1] += C[N + M - 2] / BASE; C[N + M - 2] %= BASE; } positive_bigint ans; ans.d.resize(C.size()); for (int i = 0; i < C.size(); i++){ ans[i] = C[i]; } return ans; } positive_bigint operator *=(positive_bigint &A, const positive_bigint &B){ A = A * B; return A; } struct bigint{ bool neg = false; positive_bigint a; bigint(){ } bigint(long long X): neg(X < 0), a(abs(X)){ } bigint(const positive_bigint &X, bool neg = false): neg(neg), a(X){ } bigint(const std::string &s){ if (!s.empty()){ if (s[0] == '-'){ neg = true; a = positive_bigint(s.substr(1, s.size() - 1)); } else { a = positive_bigint(s); } } } bool empty() const { return a.empty(); } int size() const { return a.size(); } int& operator [](int i){ return a[i]; } }; std::string to_string(const bigint &A){ std::string ans; if (A.neg){ ans += '-'; } ans += to_string(A.a); return ans; } std::istream& operator >>(std::istream &is, bigint &A){ std::string S; is >> S; if (S != "0"){ A = bigint(S); } return is; } std::ostream& operator <<(std::ostream &os, bigint A){ os << to_string(A); return os; } positive_bigint abs(const bigint &A){ return A.a; } int cmp(const bigint &A, const bigint &B){ if (!A.neg){ if (!B.neg){ return cmp(A.a, B.a); } else { return 1; } } else { if (!B.neg){ return -1; } else { return cmp(B.a, A.a); } } } bool operator ==(const bigint &A, const bigint &B){ return cmp(A, B) == 0; } bool operator !=(const bigint &A, const bigint &B){ return cmp(A, B) != 0; } bool operator <(const bigint &A, const bigint &B){ return cmp(A, B) < 0; } bool operator >(const bigint &A, const bigint &B){ return cmp(A, B) > 0; } bool operator <=(const bigint &A, const bigint &B){ return cmp(A, B) <= 0; } bool operator >=(const bigint &A, const bigint &B){ return cmp(A, B) >= 0; } bigint operator +(const bigint &A){ return A; } bigint operator -(const bigint &A){ bigint A2 = A; if (!A2.empty()){ A2.neg = !A2.neg; } return A2; } bigint& operator +=(bigint &A, const bigint &B){ if (A.neg == B.neg){ A.a += B.a; } else { int c = cmp(A.a, B.a); if (c > 0){ A.a -= B.a; } else if (c < 0){ A.a = B.a - A.a; A.neg = !A.neg; } else { A = 0; } } return A; } bigint operator +(const bigint &A, const bigint &B){ bigint A2 = A; A2 += B; return A2; } bigint& operator -=(bigint &A, const bigint &B){ if (A.neg != B.neg){ A.a += B.a; } else { int c = cmp(A.a, B.a); if (c > 0){ A.a -= B.a; } else if (c < 0){ A.a = B.a - A.a; A.neg = !A.neg; } else { A = 0; } } return A; } bigint operator -(const bigint &A, const bigint &B){ bigint A2 = A; A2 -= B; return A2; } bigint operator *=(bigint &A, const bigint &B){ if (A.empty() || B.empty()){ A = 0; } else { if (B.neg){ A.neg = !A.neg; } A.a *= B.a; } return A; } bigint operator *(const bigint &A, const bigint &B){ bigint A2 = A; A2 *= B; return A2; } // ----- BIGINT ----- #ifndef LOCAL #define FAST_IO #endif // ============ #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define OVERRIDE(a, b, c, d, ...) d #define REP2(i, n) for (i32 i = 0; i < (i32)(n); ++i) #define REP3(i, m, n) for (i32 i = (i32)(m); i < (i32)(n); ++i) #define REP(...) OVERRIDE(__VA_ARGS__, REP3, REP2)(__VA_ARGS__) #define PER(i, n) for (i32 i = (i32)(n) - 1; i >= 0; --i) #define ALL(x) begin(x), end(x) using namespace std; using u32 = unsigned int; using u64 = unsigned long long; using i32 = signed int; using i64 = signed long long; using f64 = double; using f80 = long double; template using Vec = vector; template bool chmin(T &x, const T &y) { if (x > y) { x = y; return true; } return false; } template bool chmax(T &x, const T &y) { if (x < y) { x = y; return true; } return false; } #ifdef INT128 using u128 = __uint128_t; using i128 = __int128_t; istream &operator>>(istream &is, i128 &x) { i64 v; is >> v; x = v; return is; } ostream &operator<<(ostream &os, i128 x) { os << (i64)x; return os; } istream &operator>>(istream &is, u128 &x) { u64 v; is >> v; x = v; return is; } ostream &operator<<(ostream &os, u128 x) { os << (u64)x; return os; } #endif [[maybe_unused]] constexpr i32 INF = 1000000100; [[maybe_unused]] constexpr i64 INF64 = 3000000000000000100; struct SetUpIO { SetUpIO() { #ifdef FAST_IO ios::sync_with_stdio(false); cin.tie(nullptr); #endif cout << fixed << setprecision(15); } } set_up_io; // ============ #ifdef DEBUGF #else #define DBG(x) (void) 0 #endif // ============ #include #include #include #include class HeavyLightDecomposition { std::vector siz; std::vector par; std::vector hea; std::vector in; std::vector out; std::vector dep; std::vector rev; template void dfs1(G &g, int v) { if (!g[v].empty() && (int) g[v][0] == par[v]) { std::swap(g[v][0], g[v].back()); } for (auto &e : g[v]) { int u = (int)e; if (u != par[v]) { par[u] = v; dfs1(g, u); siz[v] += siz[u]; if (siz[u] > siz[(int) g[v][0]]) { std::swap(g[v][0], e); } } } } template void dfs2(const G &g, int v, int &time) { in[v] = time; rev[time++] = v; for (auto &e : g[v]) { int u = (int)e; if (u == par[v]) { continue; } if (u == (int) g[v][0]) { hea[u] = hea[v]; } else { hea[u] = u; } dep[u] = dep[v] + 1; dfs2(g, u, time); } out[v] = time; } public: template HeavyLightDecomposition(G &g, int root = 0) : siz(g.size(), 1), par(g.size(), root), hea(g.size(), root), in(g.size(), 0), out(g.size(), 0), dep(g.size(), 0), rev(g.size(), 0) { assert(root >= 0 && root < (int) g.size()); dfs1(g, root); int time = 0; dfs2(g, root, time); } int subtree_size(int v) const { assert(v >= 0 && v < (int) siz.size()); return siz[v]; } int parent(int v) const { assert(v >= 0 && v < (int) par.size()); return par[v]; } int in_time(int v) const { assert(v >= 0 && v < (int) in.size()); return in[v]; } int out_time(int v) const { assert(v >= 0 && v < (int) out.size()); return out[v]; } int depth(int v) const { assert(v >= 0 && v < (int) dep.size()); return dep[v]; } int time_to_vertex(int t) const { assert(t >= 0 && t < (int) rev.size()); return rev[t]; } int head(int v) const { assert(v >= 0 && v < (int) out.size()); return hea[v]; } int la(int v, int k) const { assert(v >= 0 && v < (int) dep.size()); assert(k >= 0); if (k > dep[v]) { return -1; } while (true) { int u = hea[v]; if (in[u] + k <= in[v]) { return rev[in[v] - k]; } k -= in[v] - in[u] + 1; v = par[u]; } return 0; } int forward(int v, int dst) const { assert(v >= 0 && v < (int) dep.size()); assert(dst >= 0 && dst < (int) dep.size()); assert(v != dst); int l = lca(v, dst); if (l == v) { return la(dst, dep[dst] - dep[v] - 1); } else { return par[v]; } } int lca(int u, int v) const { assert(u >= 0 && u < (int) dep.size()); assert(v >= 0 && v < (int) dep.size()); while (u != v) { if (in[u] > in[v]) { std::swap(u, v); } if (hea[u] == hea[v]) { v = u; } else { v = par[hea[v]]; } } return u; } int dist(int u, int v) const { assert(u >= 0 && u < (int) dep.size()); assert(v >= 0 && v < (int) dep.size()); return dep[u] + dep[v] - 2 * dep[lca(u, v)]; } std::vector> path(int u, int v, bool edge) const { assert(u >= 0 && u < (int) dep.size()); assert(v >= 0 && v < (int) dep.size()); std::vector> fromu, fromv; bool rev = false; while (true) { if (u == v && edge) { break; } if (in[u] > in[v]) { std::swap(u, v); std::swap(fromu, fromv); rev ^= true; } if (hea[u] == hea[v]) { fromv.emplace_back(in[v], in[u] + (int)edge); v = u; break; } else { fromv.emplace_back(in[v], in[hea[v]]); v = par[hea[v]]; } } if (rev) { std::swap(fromu, fromv); } std::reverse(fromv.begin(), fromv.end()); fromu.reserve(fromv.size()); for (auto [x, y] : fromv) { fromu.emplace_back(y, x); } return fromu; } int jump(int u, int v, int k) const { assert(u >= 0 && u < (int) dep.size()); assert(v >= 0 && v < (int) dep.size()); assert(k >= 0); int l = lca(u, v); int dis = dep[u] + dep[v] - 2 * dep[l]; if (k > dis) { return -1; } if (k <= dep[u] - dep[l]) { return la(u, k); } else { return la(v, dis - k); } } int meet(int u, int v, int w) const { return lca(u, v) ^ lca(v, w) ^ lca(w, u); } }; // ============ struct Parser { string s; i32 it; // results Vec> tree; Vec val; Vec op; i32 root; i32 new_node() { i32 v = (i32)tree.size(); tree.push_back(Vec()); val.push_back(bigint()); op.push_back('!'); return v; } i32 number() { bool pos = true; while (it < (i32)s.size() && s[it] == '-') { pos = !pos; ++it; } string d; while (it < (i32)s.size() && isdigit(s[it])) { d.push_back(s[it]); ++it; } i32 v = new_node(); val[v] = bigint(d); if (!pos) { val[v] = -val[v]; } return v; } i32 factor() { if (s[it] == '(') { ++it; i32 v = expr(); assert(it < (i32)s.size() && s[it] == ')'); ++it; return v; } else { i32 v = number(); return v; } } i32 term() { i32 r = factor(); while (it < (i32)s.size() && s[it] == '*') { ++it; i32 u = r; i32 v = factor(); r = new_node(); op[r] = '*'; tree[r].push_back(u); tree[r].push_back(v); } return r; } i32 expr() { i32 r = term(); while (it < (i32)s.size() && (s[it] == '+' || s[it] == '-')) { if (s[it] == '+') { ++it; i32 u = r; i32 v = term(); r = new_node(); op[r] = '+'; tree[r].push_back(u); tree[r].push_back(v); } else { ++it; i32 v = term(); // negate { i32 m = new_node(); val[m] = bigint(-1LL); i32 t = new_node(); op[t] = '*'; tree[t].push_back(v); tree[t].push_back(m); v = t; } // add i32 u = r; r = new_node(); op[r] = '+'; tree[r].push_back(u); tree[r].push_back(v); } } return r; } Parser(string s) : s(s), it(0), tree(), val(), op(), root(-1) { root = expr(); } }; // 末尾から適用する bigint affine(const Vec &op, const Vec &val, const bigint &x) { assert(op.size() == val.size()); /*bigint ans = x; PER(i, op.size()) { if (op[i] == '+') { ans += val[i]; } else if (op[i] == '-') { ans -= val[i]; } else { ans *= val[i]; } } return ans;*/ // x -> ax+b auto rec = [&](auto rec, i32 l, i32 r) -> pair { if (r - l == 1) { if (op[l] == '+') { return pair(bigint(1LL), val[l]); } else if (op[l] == '-') { return pair(bigint(1LL), -val[l]); } else { return pair(val[l], bigint()); } } i32 mid = (l + r) / 2; auto [al, bl] = rec(rec, l, mid); auto [ar, br] = rec(rec, mid, r); return pair(al * ar, al * br + bl); }; auto [a, b] = rec(rec, 0, (i32)op.size()); return a * x + b; } int main() { i32 n; cin >> n; string s; cin >> s; Parser parser(s); HeavyLightDecomposition hld(parser.tree, parser.root); Vec heavy(parser.tree.size(), -1), light(parser.tree.size(), -1); REP(i, parser.tree.size()) { if (parser.tree[i].empty()) { continue; } i32 u = parser.tree[i][0], v = parser.tree[i][1]; if (hld.head(u) == u) { heavy[i] = v; light[i] = u; } else { heavy[i] = u; light[i] = v; } } auto solve = [&](auto solve, i32 v) -> bigint { if (heavy[v] == -1) { return parser.val[v]; } Vec op; Vec val; i32 cur = v; while (heavy[cur] != -1) { op.push_back(parser.op[cur]); val.push_back(solve(solve, light[cur])); cur = heavy[cur]; } return affine(op, val, solve(solve, cur)); }; cout << solve(solve, parser.root) << '\n'; }