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:
Information Graph
Finding strongly connected components - Building condensation graph
Preparing for Merge Sort
Dijkstra on sparse graphs
Optimal Polygon Perimeter
New Year Present
Parallel Programming
Dima and Figure
Newton's method for finding roots
Z-function and its calculation
Noise Level
New Year Permutation
Minimum spanning tree - Prim's algorithm
Search for a pair of intersecting segments
Kirchhoff's theorem. Finding the number of spanning trees
To Play or not to Play
Robots protection
Cow and Fields
Prefix function. Knuth–Morris–Pratt algorithm
Maximum Distance
Playing on Graph
Cinema
Minimum stack / Minimum queue
Underfail
To Hack or not to Hack
Dividing Kingdom II
Optimal Subsequences (Hard Version)
Hongcow Builds A Nation
Submask Enumeration
Chain Reaction
Pearls in a Row
Sereja and Sets