聚类计数

• 时间限制：3 秒
• 内存限制：256 MiB

题目描述

有 $n$ 台计算机。任意两台不同计算机 $i,j$ 之间有一个传输难度 $a_{i,j}$，所有无序点对的难度互不相同。

把全部计算机划分为若干非空组。一个划分合法，当且仅当对任意一个组，组内任意两台不同计算机之间的难度，都严格小于从该组任意计算机连向其他组任意计算机的难度。

对每个 $k=1,2,\ldots,n$，求恰好划分成 $k$ 组的合法方案数，答案对 $998244353$ 取模。

输入格式

第一行一个整数 $n$。

接下来 $n$ 行，每行 $n$ 个整数，表示矩阵 $a$。矩阵对称、对角线为零，且所有 $i<j$ 的 $a_{i,j}$ 两两不同。

输出格式

输出 $n$ 个整数，第 $k$ 个整数表示恰好划分成 $k$ 组的合法方案数。

样例输入 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

数据范围

$1\le n\le1500$；$a_{i,i}=0$；矩阵对称；所有上三角元素是 $1$ 到 $n(n-1)/2$ 的一个排列。