CF115D.Unambiguous Arithmetic Expression

普及/提高-

通过率：0%

AC君温馨提醒

该题目为【codeforces】题库的题目，您提交的代码将被提交至codeforces进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

Let's define an unambiguous arithmetic expression (UAE) as follows.

All non-negative integers are UAE's. Integers may have leading zeroes (for example, $0000$ and $0010$ are considered valid integers).
If $X$ and $Y$ are two UAE's, then " $(X)+(Y)$ ", " $(X)-(Y)$ ", " $(X)*(Y)$ ", and " $(X)/(Y)$ " (all without the double quotes) are UAE's.
If $X$ is an UAE, then " $-(X)$ " and " $+(X)$ " (both without the double quotes) are UAE's.You are given a string consisting only of digits ("0" - "9") and characters "-", "+", "*", and "/". Your task is to compute the number of different possible unambiguous arithmetic expressions such that if all brackets (characters "(" and ")") of that unambiguous arithmetic expression are removed, it becomes the input string. Since the answer may be very large, print it modulo $1000003$ ( $10^{6}+3$ ).

输入格式

The first line is a non-empty string consisting of digits ('0'-'9') and characters '-', '+', '*', and/or '/'. Its length will not exceed $2000$ . The line doesn't contain any spaces.

输出格式

Print a single integer representing the number of different unambiguous arithmetic expressions modulo $1000003$ ( $10^{6}+3$ ) such that if all its brackets are removed, it becomes equal to the input string (character-by-character).

输入输出样例

输入#1
```
1+2*3
```
输出#1
```
2
```
输入#2
```
03+-30+40
```
输出#2
```
3
```
输入#3
```
5//4
```
输出#3
```
0
```
输入#4
```
5/0
```
输出#4
```
1
```

输入#5

1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1

输出#5

说明/提示

For the first example, the two possible unambiguous arithmetic expressions are:

$((1)+(2))*(3)$ $(1)+((2)*(3))$For the second example, the three possible unambiguous arithmetic expressions are:

$(03)+((-(30))+(40))$ $(03)+(-((30)+(40)))$ $((03)+(-(30)))+(40)$

首页