← 返回题目列表

Codeforces · 958/D2

D2. 超空间跳跃(难)

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

现在已经过去了 125 年,但人类仍然在躲避决心毁灭人类的人形机器人种族。或者也许我们在这里混淆了一些故事......无论如何,舰队现在更小了。然而,在最近的升级中,所有导航系统都配备了更高维的线性代数跳跃处理器。

现在,为了进行跳跃,船长需要指定事件发生所在的 d 维空间的子空间。她通过为该子空间提供一组生成向量来实现这一点。

海蒂公主从m艘船的船长那里收到了这样一套。再次,她希望将超空间跳跃子空间相等的那些飞船分组。为此,她想为每艘船分配一个介于 1 和 m 之间的组号,以便当且仅当它们相应的子空间相等时,两艘船具有相同的组号(即使它们可能使用不同的向量集给出)。

帮助海蒂!

输入

输入的第一行包含两个空格分隔的整数 m 和 d (2 ≤ m ≤ 30 000, 1 ≤ d ≤ 5) – 分别是船舶的数量和完整底层向量空间的维度。接下来依次描述m个子空间。第i个子空间,对应第i艘船,描述如下:

第一行包含一个整数ki (1 ≤ ki ≤ d)。然后是 ki 行,其中第 j 行描述第 i 艘船发送的第 j 个矢量。每 j 行由 d 个空格分隔的整数 aj, j = 1, ..., d 组成,它们描述向量 $$(a_{1},a_{2},\ldots,a_{d})\in\mathbb{R}^{d}$$;它认为 |aj| ≤ 250。第 i 个子空间是这些 ki 向量的线性跨度。

输出

输出 m 个空格分隔的整数 g1, ..., gm,其中 $$g_{i} \in \{1,\ldots,m\}$$ 表示分配给第 i 艘船的组号。也就是说,对于任何 1 ≤ i < j ≤ m,以下应成立:gi = gj 当且仅当第 i 个子空间和第 j 个子空间相等。此外,序列 (g1, g2, ..., gm) 在具有该属性的所有序列中按字典顺序应该是最小的。

示例

输入 #1

8 2
1
5 0
1
0 1
1
0 1
2
0 6
0 1
2
0 1
1 0
2
-5 -5
4 3
2
1 1
0 1
2
1 0
1 0

输出 #1

1 2 2 2 3 3 3 1

注意

在示例测试用例中,第一个和最后一个子空间相等,子空间 2 到 4 相等,子空间 5 到 7 相等。

回想一下两个子空间,一个作为向量 $$v_{1}, \ldots, v_{n} \in \mathbb{R}^{d}$$ 的范围给出,另一个作为向量 $${ w _ { 1 }, \ldots, w _ { k } \in \mathbb { R } ^ { d } }$$ 的范围给出,如果每个子空间都相等向量 vi 可以写成向量 w1, ..., wk 的线性组合(即 \mathbb{R}$$ 中存在系数 $$\alpha_{1}, \ldots, \alpha_{k} \,使得 vi = α1w1 + ... + αkwk),类似地,每个向量 wi 可以写成向量 v1, ..., vn 的线性组合。

回想一下,如果存在索引 i,1 ≤ i ≤ m,则对于所有 j < i,gi < hi 且 gj = hj,则序列 (g1, g2, ..., gm) 按字典顺序小于序列 (h1, h2, ..., hm)。