← 返回题目列表

AtCoder · ttpc2019_l

L. 多项式的零点数量

中文机器翻译题面 查看原题

配点 : 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> 符号。

  • 2x
  • 0^0
  • 2^x
  • -1
  • 2^(1+2)
  • 1000000000
  • 007

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 。