TopCoder

Thumb avatar
ToMmyDong
明天全國賽呦

User's AC Ratio

100.0% (20/20)

Submission's AC Ratio

42.7% (41/96)

Description

相信大家都知道,現在流通於市面的新台幣面額常見的有1, 5, 10, 50, 100, 500, 1000。(20、200、2000元和五角並不常見)
假設過了幾百年以後,央行發行了「新新台幣」,有N種面額,分別是1, 5, 10, 50, ...如此下去的規律,請計算給定的新台幣們能湊出的不為零的金額數有多少個。

Input Format

第一行有一個正整數$1\leq N\leq 19$,代表使用的新台幣面額個數。
第二行有$N$個正整數$0\leq c_i\leq 10^ 9$,代表現在有$c_i$個第$i$種新台幣。
以下以$S$代表$c_1+\dots+c_N$

子任務(測資) 額外限制 分數
1 (0~4) $c_i < 2$ 7
2 (5~9) $S\leq 20$ 11
3 (10~14) $N\leq 7, S\leq 1000$ 16
4(10~19) $N\leq 8, S\leq 2000$ 17
5 (0~24) 無限制 49

Output Format

輸出一個整數,代表能湊出的不為零的金額個數。請將答案模1000000007後輸出。

Sample Input

4
7 0 6 1

Sample Output

95

Hints

有7個1塊,6個10塊,1個50塊,能湊出1~7,10~17,20~27,30~37,40~47,50~57,60~67,70~77,80~87,90~97,100~107,110~117共95種非零金額。

Problem Source

Problem set / Description by Paupière
題目取自2015 TOI第一階段選訓第二次模擬考pA

Subtasks

For Testdata: 0 ~ 4, Score: 7
For Testdata: 5 ~ 9, Score: 11
For Testdata: 10 ~ 14, Score: 16
For Testdata: 10 ~ 19, Score: 17
For Testdata: 0 ~ 24, Score: 49
No. Time Limit (ms) Memory Limit (KiB)
0 1000 65536
1 1000 65536
2 1000 65536
3 1000 65536
4 1000 65536
5 1000 65536
6 1000 65536
7 1000 65536
8 1000 65536
9 1000 65536
10 1100 65536
11 1000 65536
12 1000 65536
13 1000 65536
14 1000 65536
15 1500 65536
16 1500 65536
17 1500 65536
18 1500 65536
19 1500 65536
20 1000 65536
21 1000 65536
22 1000 65536
23 1000 65536
24 1000 65536