description
给定 \(n,k\)，求 \(n\) 个点的无向完全图满足其边权为 \([1,k]\) 中的正整数且其最小生成树边权和等于与 1 号点相连的边的权值和。
\(n,k\leq 250\)
solution
不妨先确定 1 号点到剩下 \(n-1\) 个点中 \(i\) 号点的边权为 \(a_i\)。
可以发现，对于其他每条边 \((x,y),(1<x<y\leq n)\)，它可取的边权的值为 \([\max(a_x,a_y),k]\)，即 \(k-\max(a_x,a_y)+1\) 个。\(a\) 数组的这种取值对答案的贡献就是 \(\prod\limits_{x}\prod\limits_{y} k-\max(a_x,a_y)+1\)。 考虑对于每个 \(a_i\) 算贡献，我们需要知道有多少个 \(a_j(j\neq i)\leq a_i\)。这引导我们把当前图中边权的上界作为 dp 状态的一维。
设 \(f_{i,j}\) 表示由 \(j+1\) 个点构成的所有边权不超过 \(i\) 的合法的无向完全图的数量。
我们有转移：
- \(f_{0,0}=1\)
- \(f_{p,i}=\sum\limits_{j=0}^i \dbinom{i}{j} f_{p-1,i-j}(k-p+1)^{j(i-j)+j(j-1)/2}\)
也就是去枚举有多少个 \(a_i\) 恰等于 \(p\)。
答案即为 \(f_{k,n-1}\)。
code
Submission #228232269 - Codeforces
标签：code,个点,CF1657E,边权,等于,号点 From： https://www.cnblogs.com/FreshOrange/p/17765407.html