Description
给定 \(N,M\)，求对于所有 \(N\) 个点的，满足恰有 \(M\) 条从小连向大的边，即 \(\sum\limits_{(u,v)\in E}[u<v]=M\) 的竞赛图，求其强连通分量的个数之和。
\(N\le 30,0\le M\le \frac{N(N-1)}{2}\)
Solution
首先有一个经典结论：
给竞赛图每个 SCC （强连通分量）缩点后，剩下的是由一条极长的链与某些前向边组成的图。
于是 SCC 的数量能够转换为链上边数 \(+1\)，也就是在链上切一刀分成左右 \(2\) 个集合的方案数 \(+1\)。
如果我们在链的开头前/结尾后也能切的话，那就变成了切一刀分成左右 \(2\) 个集合 \(A,B\) 的方案数 \(-1\)，因为边的方向始终从左到右，那么 \(A,B\) 满足 \(\forall u\in A,v\in B\)，存在 \(u\to v\) 的边。
于是我们现在考虑统计把 \(\{1,2,\cdots, n\}\) 分成两个集合 \(A,B\)（允许出现空集），使得 \(A\) 中的点始终连向 \(B\) 中的点的方案数。再减去 \(N\) 个点 \(M\) 条从小连向大的边的竞赛图个数就是答案。
设 \(f_{i,j,k}\) 表示 \(i\) 个点的竞赛图，上述 \(A\) 集合满足 \(|A|=j\)，一共有 \(k\) 条从小连向大的边的方案数。考虑添加 \(i+1\) 号点，讨论加入 \(A/B\) 中，对 \(k\) 产生的贡献：
- \(i+1\) 加入 \(A\) 集合，由于 \(A\) 始终向 \(B\) 连边，所以 \(B\) 中没有贡献；于是只要在 \(A\) 中任选 \(l\) 个点 \(u\) 满足 \(u\to i+1\) 即可贡献 \(l\)，那么 \(f_{i,j,k}\cdot \dbinom{j}{l}\to f_{i+1,j+1,k+l}\)。
- \(i+1\) 加入 \(B\) 集合，\(A\) 中所有点向 \(i+1\) 连边有 \(j\) 的贡献，在 \(B\) 中任选 \(l\) 个点满足 \(u\to i+1\) 贡献 \(l\)，那么 \(f_{i,j,k}\cdot\dbinom{i-j}{l}\to f_{i+1,j,k+l+j}\)。
现在还剩最后一步：如何统计再减去 \(N\) 个点有 \(M\) 条从小连向大的边的竞赛图个数。其实不难发现这就是 \(f_{n,0,m}\) 或者 \(f_{n,n,m}\)，因为去掉 \(A\) 向 \(B\) 连边的限制即可。
所以答案为：
复杂度 \(O(n^5)\)。
const int N = 35;
const int P = 998244353;
int n, m, f[N][N][N * N], C[N][N];
signed main() {
n = rd(), m = rd();
C[0][0] = 1;
for (int i = 1; i <= n; i++) {
C[i][0] = 1;
for (int j = 1; j <= i; j++)
C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % P;
}
f[0][0][0] = 1;
for (int i = 0; i < n; i++) {
for (int j = 0; j <= i; j++) {
for (int k = 0; k <= i * (i - 1) / 2; k++) {
for (int l = 0; l <= j; l++) (f[i + 1][j + 1][l + k] += 1ll * f[i][j][k] * C[j][l] % P) %= P;
for (int l = 0; l <= i - j; l++) (f[i + 1][j][l + k + j] += 1ll * f[i][j][k] * C[i - j][l] % P) %= P;
}
}
}
int res = 0;
for (int i = 1; i <= n; i++)
(res += f[n][i][m]) %= P;
wr(res);
return 0;
}