luogu#P7716. 「EZEC-10」Covering
「EZEC-10」Covering
题目描述
给你一个 的棋盘和 张 的纸片,编号 到 。
你可以任意选择数量在 内的纸片,并按照编号从小到大的顺序,依次横放或竖放在棋盘上。
注意:后放的纸片会覆盖在先放的纸片上。
给定最终棋盘中每个格子上的纸片编号,求满足条件的不同方案数,并对 取模。
两种方案相同,当且仅当两方案选择的纸片数量、纸片编号及每张纸片的摆放位置均相同。
输入格式
第一行一个整数 ,表示测试数据组数。
对于每组测试数据:
- 第一行五个整数 。
- 后 行每行 个整数,表示最终棋盘中每个格子上的纸片编号,若某格子未被覆盖则编号记为 。
- 数据保证至少存在一种可行的方案。
输出格式
对于每组数据:
- 一行一个整数,表示方案数对 取模的结果。
1
2 2 4 2 4
1 2
3 3
2
2
2 2 4 2 3
0 0
2 2
2 2 4 2 2
1 1
3 3
1
1
提示
【样例 1 解释】
不难发现只能取编号为 的纸片,此时共有 种方案:
,,;
,,。
【数据规模与约定】
本题采用捆绑测试。
- Subtask 1(5 points):。
- Subtask 2(10 points):。
- Subtask 3(15 points):。
- Subtask 4(20 points):。
- Subtask 5(50 points):无特殊限制。
对于 的数据,,,。