Problem
有一个 \(n\) 个点的无向完全图，边权 $ e∈[1,m]$ ，已知该图的最小生成树的权值与所有与 \(1\) 号点相连的边的边权和相同，求有多少种构图方式，答案对 \(998244353\) 取模。
\(2\leq n \leq 250 , 1 \leq m \leq 250\) 。
Input
一行两个整数 \(n\)，\(k\)。
Output
一行一个整数表示答案。
Sample
Input 1
3 2
Output 1
5
Input 2
4 4
Output 2
571
Input 3
6 9
Output 3
310640163
Input 4
42 13
Output 4
136246935
Solution
比较难想的DP题。
考虑定义 \(f_{i,j}\) 表示当前给与 \(1\) 相连的 \(j\) 条边分配了权值，每条边权值在 \([1,i]\) 之间的方案数。
由题意可以得到，对于一条边 \((x, y)\)，若 \(x \neq 1\) 且 \(y \neq 1\)，则该边的权值 \(W_{x,y} \geq W_{1, x}\) 且 \(W_{x,y} \geq W_{1, y}\)。
\(n，k\) 都很小，可以考虑两层循环枚举状态，一层循环进行转移。
假设我们已知为 \(f_{i - 1,j}\) 的答案，从剩下的 \(n-1-j\) 条边中选出 \(k\) 条边赋值为 \(i\)，容易可以得到转移：
\(f_{i,j+k} = f_{i,j+k}+ f_{i-1,j} * c_{n-j-1,k} * Pow(m-i+1,j*k+k*(k-1)/2)\)
其中 \(c_{n-j-1,k}\) 为从 \(n-j-1\) 条边中选出 \(k\) 条边的方案数。（组合数）
加入的这 \(k\) 条边之间连出的 \(k*(k-1)/2\) 条边以及这 \(k\) 条边与前面 \(j\) 条边之间连出的 \(j\times k\) 条边的权值都必须在 \([i,m]\) 之间，每一条边都有 \(m-i+1\) 种选择，还需乘上这部分的贡献。
最后 \(f_{m,n-1}\) 即为答案，权值不超过 \(i\)，分配了 \(n-1\) 条边。
代码：
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int kmax = 255;
const int Mod = 998244353;
int n, m;
long long c[kmax][kmax];
long long f[kmax][kmax];
long long Pow(long long x, long long y) {
long long r = 1;
for (; y; y >>= 1) {
if (y & 1) r = r * x % Mod;
x = x * x % Mod;
}
return r;
}
void Init() { // 预处理组合数
c[0][0] = 1;
for (int i = 1; i < kmax; i++) {
c[i][0] = 1;
for (int j = 1; j <= i; j++) {
c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % Mod;
}
}
}
int main() {
Init();
cin >> n >> m;
f[0][0] = 1;
for (int i = 1; i <= m; i++) {
for (int j = 0; j < n; j++) {
for (int k = 0; k < n - j; k++) {
f[i][j + k] = (f[i][j + k] + f[i - 1][j] * c[n - j - 1][k] % Mod * Pow(m - i + 1, j * k + k * (k - 1) / 2) % Mod) % Mod; // 直接转移，记得取模
}
}
}
cout << f[m][n - 1];
return 0;
}