A6126. 「USACO 2022.1 Platinum」Counting Haybales
编程题
省选/NOI-
知识点
题目描述
如同往常一样，奶牛 Bessie 正在 Farmer John 的牛棚里制造麻烦。FJ 有 $N$（$1≤N≤5000$) 堆草堆。对于每个 $i∈[1,N]$，第 $i$ 堆草堆有 $h_i$（$1≤h_i≤10^9$）的草。Bessie 不想让任何的草倒下来，所以她唯一可以执行的操作为：
- 如果两个相邻的草堆的高度相差恰好为 $1$，她可以将较高的草堆中最上方的草移到较低的草堆之上。
执行有限多次上述操作后，可以得到多少种不同的高度序列，对 $10^9+7$ 取模？两个高度序列被认为是相同的，如果对于所有 $i$，第 $i$ 堆草堆在两者中具有相同数量的草。
- 如果两个相邻的草堆的高度相差恰好为 $1$，她可以将较高的草堆中最上方的草移到较低的草堆之上。
执行有限多次上述操作后，可以得到多少种不同的高度序列，对 $10^9+7$ 取模？两个高度序列被认为是相同的，如果对于所有 $i$，第 $i$ 堆草堆在两者中具有相同数量的草。
输入格式
输入的第一行包含 $T$，为独立的子测试用例的数量，必须全部回答正确才能通过整个测试用例。
每个子测试用例包含 $N$，以及一个 $N$ 个高度的序列。输入保证所有子测试用例的 $N$ 之和不超过 $5000$。
每个子测试用例包含 $N$，以及一个 $N$ 个高度的序列。输入保证所有子测试用例的 $N$ 之和不超过 $5000$。
输出格式
输出 $T$ 行，每行输出一个子测试用例的答案。
输入输出样例
输入 #1
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
输出 #1
4 4 5 15 9 8 19
说明/提示
- 测试点 1-3 满足 $N≤10$。
- 测试点 4 满足对于所有 $i$，有 $1≤h_i≤3$。
- 测试点 5-7 满足对于所有 $i$，有 $|h_i−i|≤1$。
- 测试点 8-10 满足对于所有 $i$，有 $1≤h_i≤4$，且 $N≤100$。
- 测试点 11-13 满足 $N≤100$。
- 测试点 14-17 满足 $N≤1000$。
- 测试点 18-21 没有额外限制。
- 测试点 4 满足对于所有 $i$，有 $1≤h_i≤3$。
- 测试点 5-7 满足对于所有 $i$，有 $|h_i−i|≤1$。
- 测试点 8-10 满足对于所有 $i$，有 $1≤h_i≤4$，且 $N≤100$。
- 测试点 11-13 满足 $N≤100$。
- 测试点 14-17 满足 $N≤1000$。
- 测试点 18-21 没有额外限制。