Counting Haybales

题目描述

和往常一样，奶牛 Bessie 又在 Farmer John 的谷仓里捣乱。FJ 有 $N$ ($1\leq N \leq 5000$) 堆干草捆。对每个 $i\in [1,N]$，第 $i$ 堆有 $h_i$ ($1\le h_i\le 10^9$) 个干草捆。Bessie 不希望有干草捆掉落，因此她唯一能进行的操作如下： 如果两堆相邻干草堆的高度恰好相差 1，她可以将较高那堆的最上面的一个干草捆移动到较矮那堆上。 在有限次执行上述操作后，一共能得到多少种不同的配置？答案对 $10^9+7$ 取模。 如果对所有 $i$，两种配置中第 $i$ 堆的干草捆数量都相同，则认为这两种配置相同。

输入格式

第一行包含 $T$ ($1\le T\le 10$)，表示相互独立的测试用例数量；要使输入被正确解决，必须解决所有测试用例。 每个测试用例包含 $N$，随后是一串长度为 $N$ 的高度序列。 保证所有测试用例中 $N$ 的总和不超过 $5000$。

输出格式

请输出 $T$ 行，每行对应一个测试用例。

7
4
2 2 2 3
4
3 3 1 2
4
5 3 4 2
6
3 3 1 1 2 2
6
1 3 3 4 1 2
6
4 1 2 3 5 4
10
1 5 6 6 6 4 2 3 2 5

4
4
5
15
9
8
19

提示

对于第一个测试用例，可能的四种配置为：

对于第二个测试用例，可能的四种配置为：

计分（SCORING）： 输入 1-3 满足 $N\le 10$。 输入 4 满足对所有 $i$ 都有 $1\le h_i\le 3$。 输入 5-7 满足对所有 $i$ 都有 $|h_i-i|\le 1$。 输入 8-10 满足对所有 $i$ 都有 $1\le h_i\le 4$ 且 $N\le 100$。 输入 11-13 满足 $N\le 100$。 输入 14-17 满足 $N\le 1000$。 输入 18-21 不满足额外限制。 题目贡献者：Daniel Zhang

标签: USACO|2022|Platinum

来源

USACO|2022|Platinum