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:
Little Artem and Random Variable
Beautiful Bracket Sequence (hard version)
Sereja ans Anagrams
Biridian Forest
Binary Exponentiation
Circle of Numbers
One-Way Reform
Businessmen Problems
Wilbur and Array
Adam and Tree
Limericks
Maximum Distance
Smallest Word
AND Segments
Kate and imperfection
Unusual Graph
Robot Rapping Results Report
Maximum Flow
Lowest Common Ancestor - Binary Lifting
Radio stations
Tree and XOR
Alyona and a Narrow Fridge
Rectangle Puzzle
The Tower is Going Home
A Trivial Problem
Height All the Same
Yui and Mahjong Set
And after happily lived ever they
Cookie Clicker
Wise Men (Hard Version)
New Year and Old Property
Bad Cryptography