dp + 组合数学
神仙题，垃圾$luogu$，这题就评个蓝，看不起谁呢。
题意非常的简单，有一个$n$个点的完全图，点权的值域为$[1,k]$，这个图的最小生成树的点权和等于所有点到$1$节点的最小距离，问这种图的个数，对$998244353$取模。
总所周知，题目描述越简单，其本身越难（大雾）
Solution
首先发现这个图的其中一颗最小生成树显然是以$1$为中心节点的菊花图，然后对于任意不为$1$两点$i,j$ ，显然满足$val_{i,j} \ge \max(val_{1,i},val_{1,j})$。
其中$val_{i,j}$表示$i$到$j$的边权。
我们用一个数列$A$来表示$val_{1,2},val_{1,3}\dots val_{1,n}$，那么我们便有$k^{n-1}$种 $A$，其答案显然等于：
$$
\sum_A \prod_{2 \le i<j\le n}(k-\max(A_i,A-j)+1)
$$
这样显然是不方便的，可以发现，我们无论求最大生成树，还是求最小生成树，其方案数都不会变（约束形式相同，只是符号相反），于是我们改为求最大生成树，那么当约束符号切换时，答案就变为：
$$
\sum_A\prod_{2\le i < j \le n} \min(A_i,A_j)
$$
形式虽然好看了许多，但显然还是不可做，继续考虑转化。
显然$A$中的数无论怎么排布都不会改变答案，我们设计数数组$cnt_i$表示$A$中值为$i$的个数。
那么答案又等于：
$$
\sum_{cnt_1+\dots cnt_k =n}\prod_{i=1}^kC_{n-\sum_{j=i+1}^kcnt_j-1}^{cnt_i}\cdot i^{\frac{cnt_i\cdot (cnt_i-1)}{2}+ cnt_i\cdot\sum_{j=i+1}^k cnt_j}
$$
$i$的次幂分别表示相同数内自由组合以及与更大的数自由组合。
可以做到$O(n^2k\log n)$或者$O(n^2k)$，是否带$log$主要取决于快速幂的实现（是否使用光速幂）。
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
| #include<bits/stdc++.h>
#define PII pair<int, int>
#define LL long long
using namespace std;
template <class T>
inline void read(T &res)
{
res = 0; bool flag = 0;
char c = getchar();
while(c < '0' || '9' < c) {if(c == '-') flag = 1; c = getchar();}
while('0' <= c && c <= '9') res = (res << 3) + (res << 1) + (c ^ 48), c = getchar();
if(flag) res = -res;
}
template <class T, class ...ARC>
inline void read(T &res, ARC &...com){ read(res), read(com...); }
template <class T>
void write(T res)
{
if(res < 0) putchar('-'), res = -res;
if(res > 9) write(res / 10);
putchar(res % 10 + '0');
}
template <>
inline void write(char c) { putchar(c); }
template <>
inline void write(char *s) { while(*s) putchar(*s ++);}
template <class T, class ...ARC>
inline void write(T res, ARC ...com) { write(res), write(com...); }
const int N = 305, mod = 998244353;
int n, m, T;
int C[N][N];
inline void init()
{
for(int i = 0;i < N;i ++) C[i][0] = 1;
for(int i = 1;i < N;i ++)
for(int j = 1;j <= i;j ++)
C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % mod;
}
int f[N][N];
inline int qpow(int x, int k)
{
int res = 1;
while(k)
{
if(k & 1) res = 1ll * res * x % mod;
k >>= 1;
x = 1ll * x * x % mod;
}
return res;
}
int main()
{
read(n, m);
init();
f[m + 1][0] = 1;
for(int i = m;i >= 0;i --)
for(int j = 0;j <= n - 1;j ++)
for(int k = 0;k <= j;k ++)
f[i][j] = (f[i][j] + 1ll * f[i + 1][j - k] * C[n - 1 - (j - k)][k] % mod * qpow(i, k * (k - 1) / 2 + k * (j - k)) % mod) % mod;
write(f[1][n - 1]);
return 0;
}
|