CF1109D Sasha and Interesting Fact from Graph Theory

这个 \(D\) 题比赛切掉的人基本上是 \(C\) 题的 \(5,6\) 倍...果然数学计数问题比数据结构更受欢迎...

• 以下大致翻译自官方题解.
• 枚举 \(a\to b\) 路径上边的数目,记为 \(edges\) .
• 先来考虑给定的两个点路径上的 \(edges-1\) 个点(不含 \(a,b\) )和 \(edge\) 条边.
  • 节点有\(edges-1\)个,顺序不同则最后的树不同,所以方案数为 \(A(n-2,edges-1)\) .
  • 边有 \(edges\) 条,边权 \(v\) 需满足\(v \in \mathbb{N_+},v_1+v_2+...+v_{edges-1}+v_{edges}=m\).用隔板法可知方案数,即解的组数为 \(C(m-1,edges-1)\).
• 再来考虑其它的 \(n-edges-1\) 个点和 \(n-edges-1\) 条边.
  • 由于其它边的边权显然不影响合法性,可以随意赋 \([1,m]\) 内的整数值,方案数为 \(m^{n-edges-1}\).
  • 剩下的点我们需要使它们形成一个森林,并将每颗树挂在 \(a\to b\) 这 \(edges+1\) 个点上.这等价于所有的 \(n\) 个点形成一个 \(edges+1\) 颗树的森林,那 \(edges+1\) 个点都属于不同的树,然后将这 \(edges+1\) 个点连接起来.根据广义\(Cayley\)定理,方案数为 \((edges+1) \cdot n^{n-edges-2}\) .

广义 \(Cayley\) 定理:

\(n\) 个标号节点形成一个有 \(k\) 颗树的森林,使得给定的 \(k\) 个点没有两个点属于同一颗树的方案数为\(k\cdot n^{n-k-1}.\)

证明可以用归纳法,对 \(n\) 归纳,枚举节点 \(1\) 的邻居即可得递推式,进而得出证明.

• 那么我们就得到了在 \(edges\) 确定的情况下的答案:

\[ f(edges)=A(n-2,edges-1) \cdot C(m-1,edges-1)\cdot m^{n-edges-1} \cdot (edges+1) \cdot n^{n-edges-2}. \]

• 线性预处理 \(m,n​\) 的幂,阶乘及阶乘逆元,枚举 \(edges​\) 统计答案,时间复杂度为 \(O(n+m)\).