#P12678. [集训队互测2025day10]骨牌覆盖
[集训队互测2025day10]骨牌覆盖
对于一个长度为 的非负整数序列 ,考虑 行的棋盘,其中第 行从第 列到第 列,所有行左对齐。若存在一种用 和 的多米诺骨牌覆盖整个棋盘的方式,则称序列 是好的。
给出一个长度为 的非负整数序列 ,求有多少个 满足 且 是好的,即这些行组成的左对齐棋盘能被多米诺骨牌完全覆盖。每块骨牌覆盖两个边相邻的格子,所有格子恰被覆盖一次。长度为 的行不含格子,空棋盘可以覆盖。
输入格式
第一行一个正整数 ,表示测试数据组数。
接下来对于每组数据,输入两行:
第一行一个正整数 。
第二行 个非负整数 。
输出格式
对于每组数据,输出一行一个非负整数,表示答案。
样例
样例 1 输入
9
5
5 6 6 5 3
9
3 7 1 8 4 4 0 6 9
3
3 1 0
3
3 0 1
3
2 0 2
1
0
10
4 7 6 6 7 6 1 2 5 5
6
5 5 5 4 3 3
6
6 4 4 6 4 1
样例 1 输出
7
22
3
1
6
1
12
7
15
样例 1 说明
对于第一组数据,,合法的 有:,,,,,,。
样例 2
见下发文件。
数据范围
对于所有数据,满足 ,,,。
- subtask 1(5%):。
- subtask 2(20%):,。
- subtask 3(20%):。
- subtask 4(20%):。
- subtask 5(35%):无特殊限制。