Drought

题目描述

由于干旱，Farmer John 牧场里的草都干枯了。在经历数小时的绝望与沉思之后，FJ 想出了一个绝妙的主意：购买玉米来喂他珍贵的奶牛。

FJ 的 $N$ 头奶牛（$1 \leq N \leq 100$）排成一列，第 $i$ 头奶牛有一个非负整数饥饿值 $h_i$。由于 FJ 的奶牛很合群并坚持一起吃饭，FJ 能降低奶牛饥饿值的唯一方式是选择两头相邻的奶牛 $i$ 和 $i+1$，分别给它们各喂一袋玉米，使得它们的饥饿值都减少 1。

FJ 想要持续喂奶牛，直到所有奶牛的饥饿值都变成相同的非负值。尽管他不知道奶牛们确切的饥饿值，但他知道每头奶牛饥饿值的一个上界；具体而言，第 $i$ 头奶牛的饥饿值 $h_i$ 至多为 $H_i$（$0\le H_i\le 1000$）。你的任务是统计满足这些上界的饥饿值 $N$ 元组 $[h_1,h_2,\ldots,h_N]$ 的数量，并且对于这些元组，FJ 需要能够实现他的目标。答案对 $10^9+7$ 取模。

输入格式

第一行包含 $N$。 第二行包含 $H_1,H_2,\ldots,H_N$。

输出格式

输出满足条件的饥饿值 $N$ 元组数量，对 $10^9+7$ 取模。

3
9 11 7

241

4
6 8 5 9

137

提示

共有 $(9+1)\cdot (11+1)\cdot (7+1)$ 个与 $H$ 一致的 $3$ 元组 $h$。 其中一个元组是 $h=[8,10,5]$。在这种情况下，可以让所有奶牛的饥饿值相等：给奶牛 $2$ 和 $3$ 各喂两袋玉米，然后给奶牛 $1$ 和 $2$ 各喂五袋玉米，最终每头奶牛的饥饿值都变为 $3$。 另一个元组是 $h=[0,1,0]$。在这种情况下，不可能让奶牛的饥饿值相等。 SCORING: $N$ 在编号为偶数的测试中为偶数，在编号为奇数的测试中为奇数。 测试 3 和 4 满足 $N\le 6$ 且 $H_i \le 10$。 测试 5 到 10 满足 $N\le 50$ 且 $H_i \le 100$。 测试 11 到 20 没有进一步的限制。 题目来源：Arpan Banerjee 和 Benjamin Qi

标签: USACO|2022|Gold

来源

USACO|2022|Gold