811 . 階梯數字

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

User's AC Ratio

0.0% (0/1)

Submission's AC Ratio

0.0% (0/9)

Tags

apcsc apcsc-dp

Description

波露特石最近在學習程式語言，他對一些特別的正整數很有興趣，他發現一些十進數的每一位數已排好順序，從高位數往低位數看過去，每一位數字只會相等或變大，例如：$9, 234, 777, 11222233$ 等數字都有這性質，他稱這些數字為階梯數字。給定一正整數 $N$，阿明想知道不大於 $N$ 的階梯數字總共有幾個，請注意本題只算正整數，所以 $0$ 不算階梯數字，而且階梯數字不會以 $0$ 開始。請幫波露特石寫計算階梯數字的個數。

Input Format

輸入只包含一個正整數 $N$。

  • $N \leq 10^ {100000}$

Output Format

請輸出一個整數代表不大於 $N$ 的階梯數字個數，因為答案可能很大，請將答案 $\mod 10^ 9 + 7$ 之後輸出。

Sample Input 1

22

Sample Output 1

19

Sample Input 2

2345

Sample Output 2

429

Hints

Problem Source

APCS 歷屆加強

Subtasks

No. Testdata Range Constraints Score
1 0~1 範例測資 0
2 0~10 $N \leq 10000$ 8
3 0~19 $N \leq 10^ {18}$ 27
4 20~27 $N = a \times 10^ b \leq 10^ {100000}, 0 \leq a < 10$ 27
5 0~36 無額外限制 38

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 524288 65536 1 2 3 5
1 1000 524288 65536 1 2 3 5
2 1000 524288 65536 2 3 5
3 1000 524288 65536 2 3 5
4 1000 524288 65536 2 3 5
5 1000 524288 65536 2 3 5
6 1000 524288 65536 2 3 5
7 1000 524288 65536 2 3 5
8 1000 524288 65536 2 3 5
9 1000 524288 65536 2 3 5
10 1000 524288 65536 2 3 5
11 1000 524288 65536 3 5
12 1000 524288 65536 3 5
13 1000 524288 65536 3 5
14 1000 524288 65536 3 5
15 1000 524288 65536 3 5
16 1000 524288 65536 3 5
17 1000 524288 65536 3 5
18 1000 524288 65536 3 5
19 1000 524288 65536 3 5
20 1000 524288 65536 4 5
21 1000 524288 65536 4 5
22 1000 524288 65536 4 5
23 1000 524288 65536 4 5
24 1000 524288 65536 4 5
25 1000 524288 65536 4 5
26 1000 524288 65536 4 5
27 1000 524288 65536 4 5
28 1000 524288 65536 5
29 1000 524288 65536 5
30 1000 524288 65536 5
31 1000 524288 65536 5
32 1000 524288 65536 5
33 1000 524288 65536 5
34 1000 524288 65536 5
35 1000 524288 65536 5
36 1000 524288 65536 5
Submit
Back to Top