| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 193 | 93 | 67 | 45.578% |
The grass has dried up in Farmer John's pasture due to a drought. After hours of despair and contemplation, FJ comes up with the brilliant idea of purchasing corn to feed his precious cows.
FJ’s $N$ (1ドル \leq N \leq 100$) cows are arranged in a line such that the $i$th cow in line has a non-negative integer hunger level of $h_i$. As FJ’s cows are social animals and insist on eating together, the only way FJ can decrease the hunger levels of his cows is to select two adjacent cows $i$ and $i+1$ and feed each of them a bag of corn, causing each of their hunger levels to decrease by one.
FJ wants to feed his cows until all of them have the same non-negative hunger level. Although he doesn't know his cows' exact hunger levels, he does know an upper bound on the hunger level of each cow; specifically, the hunger level $h_i$ of the $i$-th cow is at most $H_i$ (0ドル\le H_i\le 1000$).
Your job is to count the number of $N$-tuples of hunger levels $[h_1,h_2,\ldots,h_N]$ that are consistent with these upper bounds such that it is possible for FJ to achieve his goal, modulo 10ドル^9+7$.
The first line contains $N$.
The second line contains $H_1,H_2,\ldots,H_N$.
The number of $N$-tuples of hunger levels modulo 10ドル^9+7$.
3 9 11 7
241
There are $(9+1)\cdot (11+1)\cdot (7+1)$ 3ドル$-tuples $h$ that are consistent with $H$.
One of these tuples is $h=[8,10,5]$. In this case, it is possible to make all cows have equal hunger values: give two bags of corn to both cows 2ドル$ and 3ドル,ドル then give five bags of corn to both cows 1ドル$ and 2ドル,ドル resulting in each cow having a hunger level of 3ドル$.
Another one of these tuples is $h=[0,1,0]$. In this case, it is impossible to make the hunger levels of the cows equal.
4 6 8 5 9
137