P6980: 清点干草捆
传统题
1.000s
时间限制
256MB
内存限制
1 提交
0 解决
【题目描述】
【题目描述】
如同往常一样，奶牛 Bessie
正在 Farmer John 的牛棚里制造麻烦。FJ 有 N (1≤N≤5000)
堆草堆。对于每个 i∈[1,N]，第 i
堆草堆有 hi（1≤hi≤10
^9
）的草。Bessie
不想让任何的草倒下来，所以她唯一可以执行的操作为：
l
如果两个相邻的草堆的高度相差恰好为 1
，她可以将较高的草堆中最上方的草移到较低的草堆之上。
执行有限多次上述操作后，可以得到多少种不同的高度序列，对 10
^9+7
取模？两个高度序列被认为是相同的，如果对于所有 i，第 i
堆草堆在两者中具有相同数量的草。
【
输入格式】
（从终端 /
标准输入读入）：
输入的第一行包含 T
，为独立的子测试用例的数量，必须全部回答正确才能通过整个测试用例。
每个子测试用例包含 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
【样例说明】
对于第一个子测试用例，四个可能的高度序列为：
(2,2,2,3),(2,2,3,2),(2,3,2,2),(3,2,2,2).
对于第二个子测试用例，四个可能的高度序列为：
(2,3,3,1),(3,2,3,1),(3,3,2,1),(3,3,1,2).
【
测试点性质】
：
测试点 1-3
满足 N≤10。
测试点 4
满足对于所有 i，有 1≤hi≤3
。
测试点 5-7
满足对于所有 i
，有 |hi−i|≤1。
测试点 8-10
满足对于所有 i，有1≤hi≤4
，且 N≤100
。
测试点 11-13
满足 N≤100。
测试点 14-17
满足N≤1000。
测试点 18-21
没有额外限制。