← 返回题目列表

Codeforces · 1408/G

G. 聚类计数

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

公司网络中有 $$$n$$$ 台计算机。它们的编号从 $$$1$$$ 到 $$$n$$$。

对于每对两台计算机 $$$1 \leq i < j \leq n$$$,您知道值 $$$a_{i,j}$$$:在计算机 $$$i$$$ 和 $$$j$$$ 之间发送数据的难度。 $$$i<j$$$ 的所有值 $$$a_{i,j}$$$ 都不同。

您希望将所有计算机分成 $$$k$$$ 集合 $$$A_1、A_2、\ldots、A_k$$$,以满足以下条件:

- 对于每台计算机 $$$1 \leq i \leq n$$$ 恰好有一组 $$$A_j$$$,使得 $$$i \in A_j$$$;
- 对于每两对计算机 $$$(s, f)$$$ 和 $$$(x, y)$$$ ($$$s \neq f$$$, $$$x \neq y$$$),使得 $$$s$$$, $$$f$$$, $$$x$$$ 来自同一组,但 $$$x$$$ 和 $$$y$$$ 来自同一组不同的集合,$$$a_{s,f} < a_{x,y}$$$。

对于每个 $$$1 \leq k \leq n$$$ 找到将计算机划分为 $$$k$$$ 组的方法数量,以便满足所有必需的条件。这些值可能很大,因此您需要通过对 $$$998\,244\,353$$$ 求模来找到它们。

输入

第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 1500$$$):计算机数量。

接下来的 $$$n$$$ 行的第 $$$i$$$ 包含 $$$n$$$ 整数 $$$a_{i,1}, a_{i,2}, \ldots, a_{i,n}$$$($$$0 \leq a_{i,j} \leq \frac{n (n-1)}{2}$$$)。

保证:

- 对于所有 $$$1 \leq i \leq n$$$ $$$a_{i,i} = 0$$$;
- 对于所有 $$$1 \leq i < j \leq n$$$ $$$a_{i,j} > 0$$$;
- 对于所有 $$$1 \leq i < j \leq n$$$ $$$a_{i,j} = a_{j,i}$$$;
- $$$i <j$$$ 的所有 $$$a_{i,j}$$$ 都是不同的。

输出

打印 $$$n$$$ 整数:其中第 $$$k$$$ 应该等于将计算机划分为 $$$k$$$ 组的可能方法的数量,以便满足所有必需的条件,模 $$$998\,244\,353$$$。

示例

输入 #1

4
0 3 4 6
3 0 2 1
4 2 0 5
6 1 5 0

输出 #1

1 0 1 1

输入 #2

7
0 1 18 15 19 12 21
1 0 16 13 17 20 14
18 16 0 2 7 10 9
15 13 2 0 6 8 11
19 17 7 6 0 4 5
12 20 10 8 4 0 3
21 14 9 11 5 3 0

输出 #2

1 1 2 3 4 3 1

注意

以下是在第二个示例中将所有计算机分为 $$$4$$$ 组的所有可能方法:

- $$$\{1, 2\}, \{3, 4\}, \{5\}, \{6, 7\}$$$;
- $$$\{1\}, \{2\}, \{3, 4\}, \{5, 6, 7\}$$$;
- $$$\{1, 2\}, \{3\}, \{4\}, \{5, 6, 7\}$$$.