#PU1185. USACO 2022 January Contest, Gold — Problem 1. Drought

    ID: 1491 传统题 2000ms 256MiB 尝试: 0 已通过: 0 难度: 提高+/省选- 上传者: 标签>USACO赛事:jan22来源:usaco.orgscoring:equal_test_cases枚举

USACO 2022 January Contest, Gold — Problem 1. Drought

USACO 2022 January Contest, Gold — Problem 1. Drought

题目描述

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 NN (1≤N≤1001 \leq N \leq 100) cows are arranged in a line such that the iith cow in line has a non-negative integer hunger level of hih_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 ii and i+1i+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 hih_i of the ii-th cow is at most HiH_i (0≤Hi≤10000\le H_i\le 1000). Your job is to count the number of NN-tuples of hunger levels [h1,h2,…,hN][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 109+710^9+7.

输入格式

The first line contains NN. The second line contains H1,H2,…,HNH_1,H_2,\ldots,H_N.

输出格式

The number of NN-tuples of hunger levels modulo 109+710^9+7.

数据范围

NN is even in even-numbered tests and odd in odd-numbered tests. Tests 3 and 4 satisfy N≤6N\le 6 and Hi≤10H_i \le 10. Tests 5 through 10 satisfy N≤50N\le 50 and Hi≤100H_i \le 100. Tests 11 through 20 satisfy no further constraints. Problem credits: Arpan Banerjee and Benjamin Qi

样例

样例 1

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.

样例 2

4
6 8 5 9
137