Consider the following grammar:
- <expression> ::= <term> | <expression> ‘+’ <term>
- <term> ::= <number> | <number> ‘-‘ <number> | <number> ‘(‘ <expression> ‘)’
- <number> ::= <pos_digit> | <number> <digit>
- <digit> ::= ‘0’ | <pos_digit>
- <pos_digit> ::= ‘1’ | ‘2’ | ‘3’ | ‘4’ | ‘5’ | ‘6’ | ‘7’ | ‘8’ | ‘9’
This grammar describes a number in decimal system using the following rules:
- <number> describes itself,
- <number>-<number> (l-r, l ≤ r) describes integer which is concatenation of all integers from l to r, written without leading zeros. For example, 8-11 describes 891011,
- <number>(<expression>) describes integer which is concatenation of <number> copies of integer described by <expression>,
- <expression>+<term> describes integer which is concatenation of integers described by <expression> and <term>.
For example, 2(2-4+1)+2(2(17)) describes the integer 2341234117171717.
You are given an expression in the given grammar. Print the integer described by it modulo 109 + 7.
Input
The only line contains a non-empty string at most 105 characters long which is valid according to the given grammar. In particular, it means that in terms l-r l ≤ r holds.
Output
Print single integer — the number described by the expression modulo 109 + 7.
Examples
input
8-11
output
891011
input
2(2-4+1)+2(2(17))
output
100783079
input
1234-5678
output
745428774
input
1+2+3+4-5+6+7-9
output
123456789
Solution:
#include <bits/stdc++.h> using namespace std; const int MOD = 1000000007; inline void add(int &a, int b, int md = MOD) { a += b; if (a >= md) { a -= md; } } inline int mul(int a, int b, int md = MOD) { return (long long) a * b % md; } inline int power(int a, int b, int md = MOD) { int res = 1; while (b > 0) { if (b & 1) { res = mul(res, a, md); } a = mul(a, a, md); b >>= 1; } return res; } inline int inv(int x) { return power(x, MOD - 2); } struct node { int value; int len; }; node seq(int n7, int n6, int k) { int p10k = power(10, k); int t = mul(p10k, 10); int e = n6 - power(10, k, MOD - 1) + 1; if (e < 0) { e += MOD - 1; } int it1 = inv(t - 1); int sum = mul(power(t, e) + MOD - 1, it1); int z = mul(p10k, sum); int res = z; int cnt = n7 - p10k + 1; if (cnt < 0) { cnt += MOD; } add(res, mul(sum - cnt + MOD, it1)); return {res, mul(e, k + 1, MOD - 1)}; } node concat(node a, node b) { int value = mul(a.value, power(10, b.len)); add(value, b.value); return {value, (a.len + b.len) % (MOD - 1)}; } node multi(node a, int b) { if (b == 1) { return a; } if (b % 2 == 1) { return concat(multi(a, b - 1), a); } node z = multi(a, b / 2); return concat(z, z); } const int N = 100010; node prec[N]; node big_seq(int n7, int n6, int k) { node res = seq(n7, n6, k - 1); for (int i = k - 2; i >= 0; i--) { res = concat(prec[i], res); } return res; } char s[N]; int pos; node solve_exp() { int start = pos; int v7 = 0; int v6 = 0; while ('0' <= s[pos] && s[pos] <= '9') { v7 = mul(v7, 10); add(v7, s[pos] - '0'); v6 = mul(v6, 10, MOD - 1); add(v6, s[pos] - '0', MOD - 1); pos++; } int len_v = pos - start; if (s[pos] == '+') { pos++; return concat({v7, len_v}, solve_exp()); } if (s[pos] == '-') { pos++; int start2 = pos; int w7 = 0; int w6 = 0; while ('0' <= s[pos] && s[pos] <= '9') { w7 = mul(w7, 10); add(w7, s[pos] - '0'); w6 = mul(w6, 10, MOD - 1); add(w6, s[pos] - '0', MOD - 1); pos++; } int len_w = pos - start2; add(v7, MOD - 1); add(v6, (MOD - 1) - 1, MOD - 1); node v = big_seq(v7, v6, len_v); node w = big_seq(w7, w6, len_w); int diff = w.len - v.len; if (diff < 0) { diff += MOD - 1; } int real_value = w.value; add(real_value, MOD - mul(v.value, power(10, diff))); int real_len = w.len; add(real_len, (MOD - 1) - v.len, MOD - 1); if (s[pos] == '+') { pos++; return concat({real_value, real_len}, solve_exp()); } return {real_value, real_len}; } if (s[pos] == '(') { int finish = pos; pos++; node z = solve_exp(); node res = {0, 0}; for (int i = start; i < finish; i++) { res = multi(res, 10); if (s[i] != '0') { res = concat(res, multi(z, s[i] - '0')); } } pos++; if (s[pos] == '+') { pos++; return concat(res, solve_exp()); } return res; } return {v7, len_v}; } int main() { /* int real = 0; for (int i = 1; i <= 12345; i++) { real = mul(real, i <= 9 ? 10 : (i <= 99 ? 100 : (i <= 999 ? 1000 : (i <= 9999 ? 10000 : 100000)))); add(real, i); } printf("%d\n", real);*/ int v7 = 0; int v6 = 0; for (int k = 0; k < N; k++) { v7 = mul(v7, 10); add(v7, 9); v6 = mul(v6, 10, MOD - 1); add(v6, 9, MOD - 1); prec[k] = seq(v7, v6, k); } scanf("%s", s); pos = 0; node res = solve_exp(); printf("%d\n", res.value); return 0; }
Related posts:
Solve RMQ (Range Minimum Query) by finding LCA (Lowest Common Ancestor)
Generating all $K$-combinations
Dividing Kingdom
Wilbur and Strings
Factory Repairs
Optimal Polygon Perimeter
Sparse Table
A Trivial Problem
Beautiful fountains rows
Cron
Snake
Spectator Riots
Clique in the Divisibility Graph
Love "A"
Unsolvable
Ants
Aroma's Search
Bash's Big Day
Distributed Join
Finding the Eulerian path in $O(M)$
Addition on Segments
And Yet Another Bracket Sequence
Jerry's Protest
Kuroni and Impossible Calculation
Bear and Destroying Subtrees
Anti-Sudoku
Marvolo Gaunt's Ring
Well-known Numbers
Captains Mode
The Door Problem
LCM Challenge
Carrot Cakes