CF1408G Clusterization Counting

公司网络中有 $n$ 台计算机，编号从 $1$ 到 $n$。 对于每一对计算机 $1 \leq i < j \leq n$，你都知道 $a_{i,j}$ 的值：即在计算机 $i$ 和 $j$ 之间传输数据的难度。所有 $i

第一行包含一个整数 $n$（$1 \leq n \leq 1500$）：表示计算机的数量。 接下来的 $n$ 行，每行包含 $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$ 取模。

以下是第二个样例中将所有计算机分成 $4$ 个组的所有可能方案： - $\{1, 2\}, \{3, 4\}, \{5\}, \{6, 7\}$； - $\{1\}, \{2\}, \{3, 4\}, \{5, 6, 7\}$； - $\{1, 2\}, \{3\}, \{4\}, \{5, 6, 7\}$。 由 ChatGPT 4.1 翻译