a * b + c * d * eみたいに+と*のみからなる式が与えられた時に,いろんな部分文字列を高速に評価するのが本質です。
こういう変なのはad-hocにやろうとすると大体大変だしバグると詰むんですが,SegTreeで強引にやってしまえばノード2個のマージに落とせるため,(SegTreeが思考停止で書けるという前提のもとでは)思考停止で掛けてそこまでバグりません
↓頑張ってコメントを足したコードです
#include <bits/stdc++.h> using namespace std; using ll = long long; template<class T> using V = vector<T>; template<class T> using VV = V<V<T>>; constexpr ll TEN(int n) { return (n == 0) ? 1 : 10 * TEN(n-1); } //こういうのはenumを使ったほうがいいのかもしれません const int PLUS = -1; const int MUL = -2; const ll INF = TEN(9) + TEN(4); // 数式の情報を表すノードです struct D { // 数式の中に+が入っていないかのフラグです。これがtrueだと a * b * c * ... * z みたいに単一の項であることを表します bool f = true; // この数式は l + m + rですよという値です。f = trueの場合mに値が入っていて,l, rは0です ll l = 0, m = 0, r = 0; }; // 根性 D merge(D l, D r, int op) { D d; if (op == PLUS) { d.f = false; if (l.f && r.f) { d.l = l.m; d.r = r.m; d.m = 0; } else if (l.f) { d.l = l.m; d.m = min(INF, r.l + r.m); d.r = r.r; } else if (r.f) { d.l = l.l; d.m = min(INF, l.m + l.r); d.r = r.m; } else { d.l = l.l; d.m = min(INF, l.m + l.r + r.l + r.m); d.r = r.r; } } else { assert(op == MUL); d.f = l.f && r.f; if (l.f && r.f) { d.l = 0; d.m = min(INF, l.m * r.m); d.r = 0; } else if (l.f) { d.l = min(INF, l.m * r.l); d.m = r.m; d.r = r.r; } else if (r.f) { d.l = l.l; d.m = l.m; d.r = min(INF, l.r * r.m); } else { // 両方単一項ではなくて,l * rとやる場合です。 // l.l + l.m + l.r * r.l + r.m + r.r なので,l.m ~ r.mが圧縮できて以下のようになります d.l = l.l; d.m = min(INF, l.m + l.r * r.l + r.m); d.r = r.r; } } return d; } // SegTreeです,僕は定数倍が必要ないならポインタベースのほうが書きやすいと強硬に主張しています // このSegTreeの要素数は数字の個数で,葉以外のノードがそれぞれopを持っています struct Node { using NP = Node*; NP l, r; int sz; D d; // そのノードの数式の値 int op; // 葉以外が持っていて,PLUSかMULです Node(int _sz, const V<ll> &v, int off = 0) : sz(_sz) { if (sz == 1) { assert(v[off] > 0); d = D{true, 0, v[off], 0}; return; } int lsz = sz/2; l = new Node(lsz, v, off); r = new Node(sz-lsz, v, off + 2*lsz); op = v[off + 2*lsz-1];// assert(op == MUL || op == PLUS); d = merge(l->d, r->d, op); } // a番目の数字からb-1番目の数字までの数式を取り出して,評価します D get(int a, int b) { // 単位元が無いので単位元がないタイプのsegtreeを書きましょう if (b <= 0 || sz <= a) assert(false); if (a <= 0 && sz <= b) return d; if (b <= sz/2) return l->get(a, b); if (sz/2 <= a) return r->get(a-sz/2, b-sz/2); D ld = l->get(a, b); D rd = r->get(a-sz/2, b-sz/2); return merge(ld, rd, op); } }; ll n; string s; int p; ll ans; // グローバル変数で,答えはここにどんどん足しこまれていきます // vは{数字, op, 数字, op, 数字, op, 数字, ..., 数字}みたいになっています // 副作用として答えをansに足しこんで,最後に数式全体を評価した値を返します ll solve2(V<ll> v) { assert(v.size() % 2); int m = int(v.size()) / 2 + 1; // 数字の個数 auto tr = new Node(m, v); //a番目の数字からb-1番目の数字を評価して返す auto eval = [&](int a, int b) { auto d = tr->get(a, b); return min(INF, d.l + d.m + d.r); }; for (int i = 0; i < m; i++) { int l, r, a, b; l = i, r = m+1; while (r-l > 1) { int md = (l+r)/2; if (eval(i, md) < n) { l = md; } else { r = md; } } a = r; l = i; r = m+1; while (r-l > 1) { int md = (l+r)/2; if (eval(i, md) <= n) { l = md; } else { r = md; } } b = r; ans += b-a; } return eval(0, m); } // 数式全体を評価した値を返します,最後に呼んでいるsolve2(v)の内側でansに答えが足し込まれます ll solve() { V<ll> v; while (p != int(s.size()) && s[p] != ')') { char c = s[p]; if (c == '(') { p++; v.push_back(solve()); assert(s[p] == ')'); p++; continue; } if (isdigit(c)) { p++; v.push_back(c - '0'); continue; } if (c == '*') { p++; v.push_back(MUL); continue; } if (c == '+') { p++; v.push_back(PLUS); continue; } assert(false); } return solve2(v); } bool first() { cin >> n; if (!n) return false; cin >> s; p = 0; ans = 0; solve(); cout << ans << endl; return true; } int main() { while (first()) {} }