← 返回题目列表

Codeforces · 1545/C

C. AquaMoon 和排列

中文机器翻译题面 查看原题

琪露诺准备了$$$n$$$个数组,每个数组长度为$$$n$$$。每个数组都是从 $$$1$$$ 到 $$$n$$$ 的 $$$n$$$ 整数的排列。这些数组很特殊:对于所有 $$$1 \leq i \leq n$$$,如果我们取出每个数组的第 $$$i$$$ 个元素并用这些元素形成另一个长度为 $$$n$$$ 的数组,则生成的数组也是从 $$$1$$$ 到 $$$n$$$ 的 $$$n$$$ 整数的排列。换句话说,如果将这些 $$$n$$$ 数组放在一起形成一个具有 $$$n$$$ 行和 $$$n$$$ 列的矩阵,则该矩阵是拉丁方阵。

随后,琪露诺添加了额外的$$$n$$$数组,每个数组都是从$$$1$$$到$$$n$$$的$$$n$$$整数的排列。对于所有 $$$1 \leq i \leq n$$$,至少存在一个位置 $$$1 \leq k \leq n$$$,使得对于第 $$$i$$$ 数组和第 $$$(n + i)$$$ 数组,两个数组的第 $$$k$$$ 元素相同。请注意,从 $$$n + 1$$$ 到 $$$2n$$$ 索引的数组不必形成拉丁方。

另外,Cirno 确保对于所有 $$$2n$$$ 数组,没有两个数组完全相等,即。 e.对于所有索引对 $$$1 \leq i < j \leq 2n$$$,至少存在一个位置 $$$1 \leq k \leq n$$$,使得第 $$$i$$$ 和第 $$$j$$$ 数组的第 $$$k$$$ 元素不同。

最后,琪露诺随意改变了$$$2n$$$数组的顺序。

AquaMoon 调用所有大小为 $$$n$$$ 的 $$$2n$$$ 数组的子集,如果这些数组来自拉丁方,则很好。

AquaMoon 想知道存在多少好的子集。因为这个数字可能特别大,所以求它对 $$$998\,244\,353$$$ 求模。另外,她想找到任何好的子集。你能帮助她吗?

输入

输入由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 100$$$) — 测试用例的数量。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$5 \leq n \leq 500$$$)。

然后是 $$$2n$$$ 行。这些行中的第 $$$i$$$ 包含 $$$n$$$ 整数,表示第 $$$i$$$ 数组。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$500$$$。

输出

对于每个测试用例打印两行。

在第一行中,以 $$$998\,244\,353$$$ 为模打印良好子集的数量。

在第二行中,打印从 $$$1$$$ 到 $$$2n$$$ 的 $$$n$$$ 索引 — 构成良好子集的 $$$n$$$ 数组的索引(您可以按任何顺序打印它们)。如果有多个可能的答案,请打印其中任何一个。

示例

输入 #1

3
7
1 2 3 4 5 6 7
2 3 4 5 6 7 1
3 4 5 6 7 1 2
4 5 6 7 1 2 3
5 6 7 1 2 3 4
6 7 1 2 3 4 5
7 1 2 3 4 5 6
1 2 3 4 5 7 6
1 3 4 5 6 7 2
1 4 5 6 7 3 2
1 5 6 7 4 2 3
1 6 7 5 2 3 4
1 7 6 2 3 4 5
1 7 2 3 4 5 6
5
4 5 1 2 3
3 5 2 4 1
1 2 3 4 5
5 2 4 1 3
3 4 5 1 2
2 3 4 5 1
1 3 5 2 4
4 1 3 5 2
2 4 1 3 5
5 1 2 3 4
6
2 3 4 5 6 1
3 1 2 6 4 5
6 1 2 3 4 5
5 6 1 3 2 4
4 3 6 5 2 1
5 6 1 2 3 4
4 5 6 1 2 3
3 4 5 6 1 2
1 2 3 4 5 6
2 5 4 1 6 3
3 2 5 4 1 6
1 4 3 6 5 2

输出 #1

1
1 2 3 4 5 6 7
2
1 3 5 6 10
4
1 3 6 7 8 9

注意

在第一个测试用例中,良好子集的数量为 $$$1$$$。唯一的这样的子集是索引为 $$$1$$$、$$$2$$$、$$$3$$$、$$$4$$$、$$$5$$$、$$$6$$$、$$$7$$$ 的数组集合。

在第二个测试用例中,良好子集的数量为 $$$2$$$。它们是$$$1$$$、$$$3$$$、$$$5$$$、$$$6$$$、$$$10$$$ 或 $$$2$$$、$$$4$$$、$$$7$$$、$$$8$$$、$$$9$$$。