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:
Wonder Room
New Year and Social Network
Egor and an RPG game
Chip Game
AND Graph
Om Nom and Spiders
Grid Sort
Cards
Nested Rubber Bands
Dima and Game
Nastya and Scoreboard
University Classes
New Year and the Factorisation Collaboration
Professor GukiZ's Robot
Second price auction
Kay and Eternity
Ehab and Path-etic MEXs
Andrey and Problem
Almost Same Distance
Counting Skyscrapers
Finding Intersection of Two Segments
Maximum flow - Dinic's algorithm
Haar Features
K-th order statistic in O(N)
Shave Beaver!
Search the subarray with the maximum/minimum sum
Sereja and Algorithm
Developing Game
Alice and Hairdresser
Unsolvable
Game with Powers
Second best Minimum Spanning Tree - Using Kruskal and Lowest Common Ancestor