迷宫路径

题目描述

给定 n×m 个方格构成的图，每个格子都有一种地形：

有一些格子是墙，以符号 X 表示，墙不可通行。

有一些格子是空地，以符号 . 表示，空地可以通行。

请统计从左上角的方格出发，有多少种不同的路线可以以最短距离走到右下角。在行走过程中，不能进入地形为墙的方格，保证起点与终点方格地形不是墙。且行走时，只能移动到水平或垂直方向相邻的方格。

由于方案数可能很大，输出模 1,000,000,007 的余数。

输入格式

第一行：单个整数 n 与 m

第二行到第 n+1 行：第i+1 行每行有 m 个整数表示第 i 行的地形

输出格式

单个整数：表示路线方案模 1,000,000,007 的余数。

输入样例

3 3
...
.X.
...

输出样例

2

说明提示

30% 的数据，1≤n,m≤4

60% 的数据，1≤n,m≤10

100% 的数据，1≤n,m≤1000

限制

时间限制：1000ms

内存限制：512MiB

数零

题目描述

给定一个整数 n，请统计从 1 开始，到 n 为止的所有整数的十进制表示中，一共出现了多少个 0？

例如 n=100 时，1 到 100 中，只有以下数字出现过 0：

10, 20, 30, 40, 50, 60, 70, 80, 90, 100

所以总计出现 11 次。

输入格式

单个整数：表示 n。

输出格式

单个整数：表示 0 出现的次数。

输入样例

99

输出样例

9

说明提示

对于 30% 的数据，n≤100,000；

对于 60% 的数据，n≤10,000,000；

对于 100% 的数据，1≤n≤1,000,000,000,000。

限制

时间限制：1000ms

内存限制：512MiB

星星的个数

题目描述

你每天都会收集不同数量的星星贴纸。当收集到第 k 天时 (1≤k≤n)，他当天获得的贴纸数量是 k 张，而每张贴纸上印着的星星数量等于 k 这个数字的因数个数（比如数字6有4个因数：1,2,3,6，就印4颗星星）。请计算你这 n 天收集到的星星总数。

输入格式

输入一个整数 n。

输出格式

共一行，这 n 天收集到的星星总数。

输入样例#1

4

输出样例#1

23

输入样例#2

100

输出样例#2

26879

输入样例#3

10000000

输出样例#3

838627288460105

说明提示

数据范围

1 ≤ N ≤ 107

样例1说明

1× 1 + 2× 2 + 3× 2 + 4× 3 =23

限制

时间限制：1000ms

内存限制：512MiB

表达式的值

题目描述

后缀表达式，它的定义如下：

单个数字如 6，8 等都是后缀表达式；

如果 e1，e2 都是后缀表达式，则 e1  e2  +e1  e2  +、e1  e2  −e1  e2  −、e1  e2  ∗e1  e2  ∗ 都是后缀表达式；

不满足以上两条规则的表达式都不是后缀表达式。

给定一个后缀表达式（保证合法），请计算表达式的值，并输出它模 10007 的余数。

注意，为了方便起见，我们省略了除法，同时也规定在表达式中出现的数字只能由一位数构成。

输入格式

一个字符序列：表示输入的后缀表达式。每个字符间用一个空格分开。保证输入字符只可能出现 0 到 9 及 +，-，*　三种运算符，且构成一个合法的后缀表达式。

输出格式

单个数字：表示表达式的值模 10007 的余数，注意余数必须大于或等于零。

输入样例#1

3 4 +

输出样例#1

7

输入样例#2

2 3 3 + *

输出样例#2

12

输入样例#3

1 2 * 3 + 4 * 5 - 6 + 7 * 8 - 9 +

输出样例#3

148

输入样例#4

1 5 -

输出样例#4

6

说明提示

数据范围

记输入的可见字符数量为 n，

对于 50% 的数据，1≤n≤100；

对于 100% 的数据，1≤n≤100,000。

样例2解释：

2*(3+3)=12

限制

时间限制：1000ms

内存限制：512MiB