配点 : 100 点
問題文
x 以多项式的形式给出 f(x) 作为字符串表示 S 。
这里 S 是以下 BNF 表示法的 <expr> 符号。
<expr> ::= <term> | <expr> "+" <term> | <expr> "-" <term>
<term> ::= <factor> | <term> "*" <factor>
<factor> ::= <value> | <value> "^" <number>
<value> ::= <number> | "x" | "(" <expr> ")"
<number> ::= 1 以上 10^9 未満の整数 ただし先頭の 0 は省略される
符号分别表示以下含义。
x: x+:加法-:减法*:乘法,但加法+或减法-比...先计算^:幂运算,但加法+或减法-或乘法*比...先计算
例如,以下字符串可以成为上面的 <expr> 符号。
x^2+3*x^1+5- f(x) = x^2 + 3\times x^1 + 5
1+2-3+4*5- f(x) = 1 + 2 - 3 + 4 \times 5
((x^123+1)^456)^789- f(x) = \left( \left(x^{123} + 1\right)^{456}\right)^{789}
((x))- f(x) = \left(\left(x\right)\right)
1^1*1- f(x) = 1^1 \times 1
另外,以下字符串不能成为上面的 <expr> 符号。
2x0^02^x-12^(1+2)1000000000007
f(x) 可以得到第 \bmod{10^K} 在…中的零点的数量,也就是 f(n) \equiv 0 \pmod{10^K} 小于 0 以上 10^K 的整数 n 的编号。 它是
制約
- 所有输入均为整数
- 1 \leq K \leq 9
- 1 \leq |S| \leq 100
入力
输入是按以下格式从标准输入给出的。
K S
出力
f(n) \equiv 0 \pmod{10^K} 小于 0 以上 10^K 的整数 n 的个数。
入力例 1
2 x^2-x
出力例 1
4
- 输入的多项式为 f(x) = x^2 - x 。
- 如下所示,n=0, 1, 25, 76 满足条件。
- f(0) = 0
- f(1) = 0
- f(25) = 600 \equiv 0 \pmod{100}
- f(76) = 5700 \equiv 0 \pmod{100}
入力例 2
8 (((x))^234567890*1^1*1+(x^2)^2)
出力例 2
1000128
- 输入的多项式为 f(x) = \left(\left(\left(x\right)\right)^{234567890} \times 1^1 \times 1+\left(x^2\right)^2\right) 。
入力例 3
9 50+(2019-x+(x^3-x)^2019)*x^1
出力例 3
6
- 输入的多项式为 f(x) = 50+\left(2019-x+\left(x^3-x\right)^{2019}\right) \times x^1 。