#P18223. Shrooks
Shrooks
Shrooks
Shrek 想在一个 的棋盘上放置 个车,要求:
- 每行、每列恰好有一个车;
- 任意两个车的曼哈顿距离不超过 。
Donkey 已经预先放置了一些车,保证这些车中每行、每列至多一个。求将剩余车放好并满足以上要求的方案数,对 取模。预先放置的车不能移动。
位于第 行第 列和第 行第 列的两个车,其曼哈顿距离定义为 。
输入格式
第一行包含整数 ,表示测试用例个数。
每个测试用例包含两行:
- 第一行是整数 ,表示棋盘边长;
- 第二行有 个整数 。 表示第 行尚未放车;否则第 行第 列已经有车。
输出格式
对每个测试用例输出一行,包含一个整数,表示方案数对 取模的结果。
数据范围
- ;
- ;
- 所有测试用例的 之和不超过 ;
- 或 ;
- 对不同的 ,若 均不为 ,则 。
样例
6
2
1 2
3
-1 -1 -1
4
1 -1 -1 -1
5
1 -1 -1 -1 5
6
3 -1 -1 -1 -1 4
10
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1
1
4
1
0
6
92
样例说明
第一例已经放完两个车,且满足条件。第二例有四种合法放法。第三例只有一种合法补全。下面保留原题中这三例的棋盘图(第二例依次画出了全部四种放法):

第四例的两个预置车分别在 和 ,距离已经是 ,因此没有合法补全:
