#USACOC2221B. Counting Haybales

Counting Haybales

题目描述

如同往常一样,奶牛 Bessie 正在 Farmer John 的牛棚里制造麻烦。FJ 有 NN 堆草堆。对于每个 i[1,N]i\in [1,N],第 ii 堆草堆有 hih_i 的草。Bessie 不想让任何的草倒下来,所以她唯一可以执行的操作为:

  • 如果两个相邻的草堆的高度相差恰好为 11,她可以将较高的草堆中最上方的草移到较低的草堆之上。

执行有限多次上述操作后,可以得到多少种不同的高度序列,对 109+710^9+7 取模?两个高度序列被认为是相同的,如果对于所有 ii,第 ii 堆草堆在两者中具有相同数量的草。

  • 1N50001\leq N \leq 5000
  • 1hi1091\le h_i\le 10^9

输入格式

输入的第一行包含 TT,为独立的子测试用例的数量,必须全部回答正确才能通过整个测试用例。

每个子测试用例包含 NN,以及一个 NN 个高度的序列。输入保证所有子测试用例的 NN 之和不超过 50005000

输出格式

输出 TT 行,每行输出一个子测试用例的答案。

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
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-3 满足 N10N\le 10
  • 测试点 4 满足对于所有 ii,有 1hi31\le h_i\le 3
  • 测试点 5-7 满足对于所有 ii,有 hii1|h_i-i|\le 1
  • 测试点 8-10 满足对于所有 ii,有 1hi41\le h_i\le 4,且 N100N\le 100
  • 测试点 11-13 满足 N100N\le 100
  • 测试点 14-17 满足 N1000N\le 1000
  • 测试点 18-21 没有额外限制。

题目提供者

供题:Daniel Zhang