#P18626. Repair the Artwork
Repair the Artwork
Repair the Artwork
DreamGrid 有一条由 个格子组成的纸带,格子从左到右编号为 。有些格子画着他自己的图案,有些格子被 BaoBao 画上了别的图案,还有些格子是空的。他想擦掉 BaoBao 的全部图案,同时保留自己的所有图案。
每次操作可以选择一个非空区间 ,满足 ,且区间内的每个格子要么是空格,要么画着 BaoBao 的图案。然后把这个区间内的所有格子变成空格。
问:恰好进行 次操作,将所有 BaoBao 图案都擦掉的操作序列共有多少种?答案对 取模。
设两种操作序列的区间分别为 和 。只要存在一个 使得 或 ,这两个操作序列就不同。操作顺序有区别,同一个合法区间可以反复选择;选择一个已经全空的非空区间也是合法操作。
输入格式
第一行包含整数 ,表示测试用例数。
每个测试用例的第一行包含两个整数 ,分别表示纸带格子数和操作次数。
第二行包含 个整数 :
- :这个格子为空;
- :这个格子画着 DreamGrid 的图案,不能擦掉;
- :这个格子画着 BaoBao 的图案,必须最终擦掉。
数据范围
- ;
- ;
- ;
- ;
- 在一个输入文件中,至多 个测试用例满足 。
输出格式
对每个测试用例输出一行,包含合法操作序列数对 取模的结果。
样例输入 1
3
2 2
2 0
3 2
2 1 0
3 1
2 1 0
样例输出 1
8
3
1
样例解释
第一个测试用例有三个可选非空区间:[1,1]、[2,2]、[1,2]。两次选择共有九种有序序列,只有两次都选[2,2]时没有擦掉第一个格子,所以答案为8。
第二个测试用例中,不能跨过第二个格子。两次操作都选[1,1],或分别选[1,1]、[3,3]并交换先后顺序,共三种。第三个测试用例只能选[1,1]。