题意

• 给定 \(n\) 个点的带权无向完全图，点 \(i, j\) 之间的权值为 \(a_{i, j}\)，权值是一个 \(1 \sim \frac{n(n-1)}{2}\) 的排列。
• 计数把原图划分成 \(k\) 个组的方案数，满足：
  • 对于任意的 \((s, f), (x, y)\)，其中 \(s, f, x\) 同组，\(y\) 与 \(x\) 不同组 （\(s \ne f, x \ne y\)），\(a_{s, f} < a_{x, y}\)，即（对于每个组）组间边大于组内边。
• 输出一行 \(n\) 个数，对于 \(k \in [1, n]\) 求出答案，对 \(998244353\) 取模。
• \(n \le 1500\)

题解

考虑从小到大处理边。将边排序，依次在并查集上连接。

设 \(f_i\) 为某个连通块划分成 \(i\) 个组的方案数。

如果一个连通块还不是团时就已经和另一个连通块相连接，那么它不能单独成组，因为组内有比组间更大的边（还未加入）。

初始时每个点可以单独成组，因此对于每个点 \(f_1 = 1\)。连接两个连通块时直接做多项式卷积即可（不可能发生合并），加入所有边即可得到答案。

当一个连通块形成一个团时，可以单独成组，因此令 \(f_1\) 增 \(1\)。

复杂度 \(\mathcal O(n^2)\)，类似树形 DP。

#include <cstdio>
#include <cctype>
#include <algorithm>
#include <vector>
using namespace std;
using ll = long long;

namespace io {
#define File(s) freopen(s".in", "r", stdin), freopen(s".out", "w", stdout)
  const int SIZE = (1 << 21) + 1;
  char ibuf[SIZE], *iS, *iT, obuf[SIZE], *oS = obuf, *oT = oS + SIZE - 1;
  inline char getc () {return (iS == iT ? (iT = (iS = ibuf) + fread (ibuf, 1, SIZE, stdin), (iS == iT ? EOF : *iS ++)) : *iS ++);}
  inline void flush () {fwrite (obuf, 1, oS - obuf, stdout); oS = obuf;}
  inline void putc (char x) {*oS ++ = x; if (oS == oT) flush ();}
  template<class T>
  inline void read(T &x) {
    char ch; int f = 1;
    x = 0;
    while(isspace(ch = getc()));
    if(ch == '-') ch = getc(), f = -1;
    do x = x * 10 + ch - '0'; while(isdigit(ch = getc()));
    x *= f;
  }
  template<class T, class ...Args>
  inline void read(T &x, Args&... args) {read(x); read(args...);}
  template<class T>
  inline void write(T x) {
    static char stk[128];
    int top = 0;
    if(x == 0) {putc('0'); return;}
    if(x < 0) putc('-'), x = -x;
    while(x) stk[top++] = x % 10, x /= 10;
    while(top) putc(stk[--top] + '0');
  }
  template<class T, class ...Args>
  inline void write(T x, Args... args) {write(x); putc(' '); write(args...);}
  inline void space() {putc(' ');}
  inline void endl() {putc('\n');}
  struct _flush {~_flush() {flush();}} __flush;
};
using io::read; using io::write; using io::flush; using io::space; using io::endl; using io::getc; using io::putc;

const int M = 998244353;
inline int add(int x, int y) { return x + y >= M ? x + y - M : x + y; }
template <class... Args> inline int add(int x, int y, Args... args) { return add(add(x, y), args...); }
inline int sub(int x, int y) { return x - y < 0 ? x - y + M : x - y; }
inline int mul(int x, int y) { return 1LL * x * y % M; }
template <class... Args> inline int mul(int x, int y, Args... args) { return mul(mul(x, y), args...); }
inline void inc(int &x, int y=1) { x += y; if(x >= M) x -= M; }
inline void dec(int &x, int y=1) { x -= y; if(x < 0) x += M; }
inline int power(int x, int y) {
  int res = 1;
  for(; y; y>>=1, x = mul(x, x)) if(y & 1) res = mul(res, x);
  return res;
}
inline int inv(int x) { return power(x, M - 2); }

using poly = vector<int>;
poly operator*(poly a, poly b) {
  poly c(a.size() + b.size() + 1);
  for (size_t i = 0; i < a.size(); ++i)
    for (size_t j = 0; j < b.size(); ++j)
      inc(c[i + j + 1], mul(a[i], b[j]));
  return c;
}

const int N = 1505;
int fa[N], siz[N], edges[N];
poly f[N];
int find(int x) {
  return !fa[x] ? x : fa[x] = find(fa[x]);
}
void link(int x, int y) {
  x = find(x), y = find(y);
  if (x == y) {
    ++edges[x];
    if (edges[x] == siz[x] * (siz[x] - 1) / 2)
      ++f[x][0];
    return;
  }
  if (siz[x] < siz[y]) swap(x, y);
  fa[y] = x;
  siz[x] += siz[y];
  edges[x] += edges[y] + 1;
  f[x] = f[x] * f[y];
  if (edges[x] == siz[x] * (siz[x] - 1) / 2)
    ++f[x][0];
}

struct edge {
  int x, y, w;
}e[N * N / 2];

int main() {
  File("g");
  int n;
  read(n);
  fill(f + 1, f + 1 + n, poly({1}));
  fill(siz + 1, siz + 1 + n, 1);
  fill(edges + 1, edges + 1 + n, 0);
  int ec = 0;
  for (int i = 1; i <= n; ++i)
    for (int j = 1; j <= n; ++j) {
      int w; read(w);
      if (i < j) e[++ec] = {i, j, w};
    }
  sort(e + 1, e + 1 + ec, [] (edge x, edge y) {return x.w < y.w;});
  for (int i = 1; i <= ec; ++i)
    link(e[i].x, e[i].y);
  int rt = find(1);
  for (int i = 0; i < n; ++i)
    write(f[rt][i]), space();
  endl();
  return 0;
}