前言
又是随机游走？
题目分析
看到加边，可能性太多了。但是为了让步数最大化，我们可以贪心地想，肯定要往前面连，而且越前面要走的期望步数肯定越大。并且，我们不会浪费边在终点上。于是，题目转变成了 \(1 \sim n - 1\) 连向起点 \(1\) 连若干条边，使得随机游走到终点的期望步数最大。
那要如何分配这 \(m\) 条边到 \(1 \sim n - 1\) 个点呢？考虑假设已知第 \(i\) 个点向 \(1\) 连了 \(d_i\) 条边，求期望步数。设 \(f_i\) 为到了 \(i\)，还要期望多少步走到终点，显然 \(f_n = 0\)。开始喜闻乐见的推式子环节：
\[\large f_i = \cfrac{1}{d_i + 1}f_{i+1} + \cfrac{d_i}{d_i + 1}f_1+1 \]从 \(n-1\) 向前递推。
\[\begin{aligned} \large f_{n-1} &= \cfrac{1}{d_{n-1} + 1}f_{n-1+1} + \cfrac{d_{n-1}}{d_{n-1} + 1}f_1+1 \\ &= \cfrac{d_{n-1}}{d_{n-1} + 1}f_1+1 \end{aligned} \]推到 \(n-2\)。
\[\begin{aligned} \large f_{n-2} &= \cfrac{1}{d_{n-2} + 1}f_{n-1} + \cfrac{d_{n-2}}{d_{n-2} + 1}f_1 + 1 \\ &= \cfrac{1}{d_{n-2} + 1} \cdot (\cfrac{d_{n-1}}{d_{n-1} + 1}f_1 + 1) + \cfrac{d_{n-2}}{d_{n-2} + 1}f_1 + 1\\ &= \cfrac{1}{d_{n-2} + 1} \cdot \cfrac{d_{n-1}}{d_{n-1} + 1}f_1 + \cfrac{d_{n-2}}{d_{n-2} + 1}f_1 + \cfrac{1}{d_{n-2} + 1} + 1 \\ &= \cfrac{d_{n-1} + d_{n-2} \cdot (d_{n-1}+1)}{(d_{n-2} + 1) \cdot (d_{n-1} + 1)} f_1 + \cfrac{(d_{n - 2} + 1) + 1}{d_{n-2} + 1} \\ &= \cfrac{(d_{n-2} + 1) \cdot (d_{n-1}+1) - 1}{(d_{n-2} + 1) \cdot (d_{n-1} + 1)} f_1 + \cfrac{(d_{n - 2} + 1) + 1}{d_{n-2} + 1} \end{aligned} \]再推到 \(n-3\)。
\[\begin{aligned} f_{n-3} =& \cfrac{1}{d_{n-3} + 1}f_{n-2} + \cfrac{d_{n-3}}{d_{n-3} + 1}f_1+1 \\ =& {\scriptsize \cfrac{1}{d_{n-3} + 1}(\cfrac{(d_{n-2} + 1) \cdot (d_{n-1}+1) - 1}{(d_{n-2} + 1) \cdot (d_{n-1} + 1)} f_1 + \cfrac{(d_{n - 2} + 1) + 1}{d_{n-2} + 1}) + \cfrac{d_{n-3}}{d_{n-3} + 1}f_1+1} \\ =& {\scriptsize \cfrac{(d_{n-2} + 1) \cdot (d_{n-1}+1) - 1}{(d_{n-3} + 1) \cdot (d_{n-2} + 1) \cdot (d_{n-1} + 1)} f_1 + \cfrac{(d_{n - 2} + 1) + 1}{(d_{n-3} + 1) \cdot (d_{n-2} + 1)} + \cfrac{d_{n-3}}{d_{n-3} + 1}f_1+1} \\ =& {\scriptsize \cfrac{d_{n-3} \cdot (d_{n-2} + 1) \cdot (d_{n-1} + 1) + (d_{n-2} + 1) \cdot (d_{n-1}+1) - 1}{(d_{n-3} + 1) \cdot (d_{n-2} + 1) \cdot (d_{n-1} + 1)} f_1 + } \\ & {\scriptsize \cfrac{(d_{n-3} + 1) \cdot (d_{n-2}+1) + (d_{n - 2} + 1) + 1}{(d_{n-3} + 1) \cdot (d_{n-2}+1)}} \\ =& {\scriptsize \cfrac{(d_{n-3} + 1) \cdot (d_{n-2} + 1) \cdot (d_{n-1} + 1) - 1}{(d_{n-3} + 1) \cdot (d_{n-2} + 1) \cdot (d_{n-1} + 1)} f_1 + \cfrac{(d_{n-3} + 1) \cdot (d_{n-2}+1) + (d_{n - 2} + 1) + 1}{(d_{n-3} + 1) \cdot (d_{n-2}+1)}} \end{aligned} \]找到一些规律，尝试去证明。假设对于 \(i+1\) 满足：
\[ \large f_{i+1} = \cfrac{\prod \limits _ {j=i+1}^{n-1} (d_j+1)-1}{\prod \limits _ {j=i+1}^{n-1} (d_j+1)}f_1 + \cfrac{\sum \limits _ {j=i+1} ^ {n-2} \prod \limits _ {k=j} ^ {n-2}(d_k+1) + 1}{\prod \limits _ {j=i+1} ^ {n-2} (d_j+1)} \]显然该式对于 \(n-1\) 成立。尝试用归纳法推到 \(i\)。
\[ \begin{aligned} f_i &= {\scriptsize \cfrac{1}{d_i + 1}(\cfrac{\prod \limits _ {j=i+1}^{n-1} (d_j+1)-1}{\prod \limits _ {j=i+1}^{n-1} (d_j+1)}f_1 + \cfrac{\sum \limits _ {j=i+1} ^ {n-2} \prod \limits _ {k=j} ^ {n-2}(d_k+1) + 1}{\prod \limits _ {j=i+1} ^ {n-2} (d_j+1)}) + \cfrac{d_i}{d_i + 1}f_1+1 } \\ &= {\scriptsize \cfrac{\prod \limits _ {j=i+1}^{n-1} (d_j+1)-1}{\prod \limits _ {j=i}^{n-1} (d_j+1)}f_1 + \cfrac{\sum \limits _ {j=i+1} ^ {n-2} \prod \limits _ {k=j} ^ {n-2}(d_k+1) + 1}{\prod \limits _ {j=i} ^ {n-2} (d_j+1)} + \cfrac{d_i}{d_i + 1}f_1+1} \\ &= {\scriptsize \cfrac{\prod \limits _ {j=i}^{n-1} (d_j+1)-1}{\prod \limits _ {j=i}^{n-1} (d_j+1)}f_1 + \cfrac{\sum \limits _ {j=i} ^ {n-2} \prod \limits _ {k=j} ^ {n-2}(d_k+1) + 1}{\prod \limits _ {j=i} ^ {n-2} (d_j+1)}} \end{aligned} \]所以上式对于所有 \(i\) 均成立。考虑边界，推到 \(i=1\) 的时候是一个方程。
\[ f_1 = \cfrac{\prod \limits _ {j=1}^{n-1} (d_j+1)-1}{\prod \limits _ {j=1}^{n-1} (d_j+1)}f_1 + \cfrac{\sum \limits _ {j=1} ^ {n-2} \prod \limits _ {k=j} ^ {n-2}(d_k+1) + 1}{\prod \limits _ {j=1} ^ {n-2} (d_j+1)} \]解方程。
\[ {\scriptsize \left( \prod \limits _ {j=1}^{n-1} (d_j+1) \right)f_1 = \left (\prod \limits _ {j=1}^{n-1} (d_j+1)-1\right)f_1 + (d_{n-1} + 1)\left({\sum \limits _ {j=1} ^ {n-2} \prod \limits _ {k=j} ^ {n-2}(d_k+1) + 1}\right)} \]\[ f_1 = {\sum \limits _ {j=1} ^ {n-2} \prod \limits _ {k=j} ^ {n-1}(d_k+1) + (d_{n-1}+1)} \]\[ \large f_1 = \sum \limits _ {j=1} ^ {n-1} \prod \limits _ {k=j} ^ {n-1}(d_k+1) \] 标签：aligned,洛谷,limits,cdot,题解,P8989,cfrac,prod,scriptsize From： https://www.cnblogs.com/XuYueming/p/18156803