P8989
XuYueming
·
2024-04-24 19:56:55
·
题解
前言
又是随机游走？
洛谷题解宽度太窄了，所以更好的阅读体验。
题目分析
看到加边，可能性太多了。但是为了让步数最大化，我们可以贪心地想，肯定要往前面连，而且越前面要走的期望步数肯定越大。并且，我们不会浪费边在终点上。于是，题目转变成了 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 \left(\cfrac{d_{n-1}}{d_{n-1} + 1}f_1 + 1\right) + \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}\left(\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}\right) + \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}\left(\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)}\right) + \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)
于是我们可以很方便地求出期望步数，即 f_1 。但是我们还是不知道最优的 d 如何分配，考虑打表找规律。在此之前，我们不妨试着找一找 d 的性质。
首先，d 一定是单调不降的。因为显然，放在后面会给更多的 \prod 提供贡献，从而使 f_1 更大。
略证：
$$
\begin{aligned}
f_1 &= \scriptsize \sum \limits _ {j=1} ^ {n-1} \prod \limits _ {k=j} ^ {n-1}(d_k+1) \\
&= \scriptsize \sum \limits _ {j=t+2} ^ {n-1} \prod \limits _ {k=j} ^ {n-1}(d_k+1) + (d_{t+1} + 1) \prod \limits _ {k=t+2} ^ {n-1}(d_k+1) + \sum \limits _ {j=1} ^ {t} \left ( (d_t + 1)(d_{t+1} + 1) \prod \limits _ {k=j} ^ {t-1}(d_k+1) \prod \limits _ {k=t+2} ^ {n-1}(d_k+1) \right )
\end{aligned}
$$
不妨交换 $d_t$ 和 $d_{t+1}$。
$$
\begin{aligned}
f_1 &= \scriptsize \sum \limits _ {j=t+2} ^ {n-1} \prod \limits _ {k=j} ^ {n-1}(d_k+1) + ({\color{red}{d_{t}}} + 1) \prod \limits _ {k=t+2} ^ {n-1}(d_k+1) + \sum \limits _ {j=1} ^ {t} \left ( ({\color{red}{d_{t+1}}} + 1)({\color{red}{d_{t}}} + 1) \prod \limits _ {k=j} ^ {t-1}(d_k+1) \prod \limits _ {k=t+2} ^ {n-1}(d_k+1) \right )
\end{aligned}
$$
显然，因为 $d_t > d_{t+1}$，所以交换后的 $f_1$ 更优。我们可以不断进行这个过程，直到 $d$ 有序，即单调不降，$f_1$ 最大。
证毕。
其次……没其次了，打表吧。
while True:
n, m = map(int, input().split())
res = [0] * n
ans = [0] * n
maxx = 0
def dfs(now, tot, x):
global maxx, ans
if now == n - 1:
res[n - 1] = tot
tmp = 0
mul = 1
for i in range(n - 1, 0, -1):
mul *= res[i] + 1
tmp += mul
if tmp > maxx:
maxx = tmp
ans = res[::]
return
i = x
while i * (n - now) <= tot:
res[now] = i
dfs(now + 1, tot - i, i)
i += 1
dfs(1, m, 0)
print(' '.join(map(str, ans[1:])))以上是打表程序。考虑 n=20 时，不断加边对最优 d 的分配造成的影响。
m = 1: 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1
m = 2: 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1
......
m = 18: 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
m = 19: 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2
m = 20: 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2
......
m = 35: 0 1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
m = 36: 0 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
m = 37: 1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
m = 38: 1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 3
......
m = 54: 1 2 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3
m = 55: 1 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3
m = 56: 2 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3
m = 57: 2 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 4
......发现，当 m < n - 1 时，加边是从 n-1 开始放到 2 ，然后当 m \geq n - 1 时，从 n-1 开始放到 1 ，如此往复，像是在不断从右往左往序列上刷。感性理解，具体证明交给读者。
Update on 2024.6.20 更新了进一步的证明
下证任意相邻两数之差不超过 1 。
证明：
对于原先的 $f_1$：
$$
\begin{aligned}
f_1 &= \sum \limits _ {j=1} ^ {n-1} \prod \limits _ {k=j} ^ {n-1}(d_k+1) \\
&= \sum \limits _ {j=t+2} ^ {n-1} \prod \limits _ {k=j} ^ {n-1}(d_k+1) + (d_{t+1} + 1) \prod \limits _ {k=t+2} ^ {n-1}(d_k+1) + \sum \limits _ {j=1} ^ {t} \left ( (d_t + 1)(d_{t+1} + 1) \prod \limits _ {k=j} ^ {t-1}(d_k+1) \prod \limits _ {k=t+2} ^ {n-1}(d_k+1) \right ) \\
&= \sum \limits _ {j=t+2} ^ {n-1} \prod \limits _ {k=j} ^ {n-1}(d_k+1) + (d_{t+1} + 1) \prod \limits _ {k=t+2} ^ {n-1}(d_k+1) + (d_t + 1)(d_{t+1} + 1) \sum \limits _ {j=1} ^ {t} \prod \limits _ {k=j} ^ {t-1}(d_k+1) \prod \limits _ {k=t+2} ^ {n-1}(d_k+1) \\
&= \sum \limits _ {j=t+2} ^ {n-1} \prod \limits _ {k=j} ^ {n-1}(d_k+1) + \left (d_{t+1} + 1 + (d_t + 1)(d_{t+1} + 1) \sum \limits _ {j=1} ^ {t} \prod \limits _ {k=j} ^ {t-1}(d_k+1) \right ) \prod \limits _ {k=t+2} ^ {n-1}(d_k+1)
\end{aligned}
$$
后来的 $f_1$，记作 $f_1'$：
$$
f_1' = \sum \limits _ {j=t+2} ^ {n-1} \prod \limits _ {k=j} ^ {n-1}(d_k+1) + \left (d_{t+1} + (d_t + 2)d_{t+1} \sum \limits _ {j=1} ^ {t} \prod \limits _ {k=j} ^ {t-1}(d_k+1) \right ) \prod \limits _ {k=t+2} ^ {n-1}(d_k+1)
$$
那么考虑作差：
$$
\begin{aligned}
f_1' - f_1 =& \Bigg ( \Big (d_{t+1} + (d_t + 2)d_{t+1} \sum \limits _ {j=1} ^ {t} \prod \limits _ {k=j} ^ {t-1}(d_k+1) \Big ) - \\ & \Big ( d_{t+1} + 1 + (d_t + 1)(d_{t+1} + 1) \sum \limits _ {j=1} ^ {t} \prod \limits _ {k=j} ^ {t-1}(d_k+1) \Big ) \Bigg ) \prod \limits _ {k=t+2} ^ {n-1}(d_k+1) \\
=& \Bigg ( \Big ((d_t + 2)d_{t+1} - (d_t + 1)(d_{t+1} + 1) \Big ) \sum \limits _ {j=1} ^ {t} \prod \limits _ {k=j} ^ {t-1}(d_k+1) - 1 \Bigg ) \prod \limits _ {k=t+2} ^ {n-1}(d_k+1) \\
=& \Bigg ( \Big (d_{t+1} - d_t - 1 \Big ) \sum \limits _ {j=1} ^ {t} \prod \limits _ {k=j} ^ {t-1}(d_k+1) - 1 \Bigg ) \prod \limits _ {k=t+2} ^ {n-1}(d_k+1) \\
\end{aligned}
$$
由于 $d_{t+1} - d_t \geq 2$，所以 $d_{t+1} - d_t - 1 \geq 1$。考虑到 $\sum \limits _ {j=1} ^ {t}$ 里至少有一个 $\prod \limits _ {k=t} ^ {t-1} = 1$，则 $\Big (d_{t+1} - d_t - 1 \Big ) \sum \limits _ {j=1} ^ {t} \prod \limits _ {k=j} ^ {t-1}(d_k+1) \geq 1$，那么有 $f_1' - f_1 \geq 0$，也就是 $f_1'$ 是不劣于 $f_1$ 的。
如此操作，直至 $\forall t \in [1, n-2], d_t + 1 \geq d_{t+1}$。
有了如上证明，发现 \forall t \in [1, n-2], d_{t+1} - d_t \in \lbrace 0, 1 \rbrace 。有了这个性质，接下来的证明最优性就简单啦。交给读者自己证明。（中考考完再来补坑）
那么，我们分别考虑两种情况即可。
情况一
当 m < n - 1 时，d_{n - m \sim n - 1} = 1 ，其他位置 d 均为 0 。此时有：
\begin{aligned}
\large f_1 &= \sum \limits _ {j=1} ^ {n-1} \prod \limits _ {k=j} ^ {n-1}([k \geq n - m] + 1) \\
&= \sum \limits _ {j=n-m} ^ {n-1} \prod \limits _ {k=j} ^ {n-1}2 + (n-m-1) \prod \limits _ {k=n-m} ^ {n-1}2 \\
&= \sum \limits _ {j=n-m} ^ {n-1} 2 ^ {n - j} + (n-m-1) 2 ^ m \\
&= 2 ^ {m + 1} - 2 + (n-m-1) 2 ^ m \\
&= 2 ^ {m + 1} - 2 ^ m - 2 + (n-m) 2 ^ m \\
&= 2 ^ m - 2 + (n-m) 2 ^ m \\
&= (n - m + 1) 2 ^ m - 2 \\
\end{aligned}
快速幂单次 \Theta(\log m) 解决。
情况二
当 m \geq n - 1 时，d_1 = \left \lfloor \cfrac{m-(n-2)}{n-1} \right \rfloor ，m 除去第一次刷的 n-2 ，和 d_1 次的刷完整个序列，还剩下 m' = m - (n - 2) - (n - 1)d_1 次从 n-1 往左刷，故 d_{2 \sim n - 1 - m'} = d_1 +1 ，d_{n - m' \sim n - 1} = d_1 + 2 。然后推式子。
\begin{aligned}
f_1 &= \sum \limits _ {j=1} ^ {n-1} \prod \limits _ {k=j} ^ {n-1}(d_k + 1) \\
&= \prod \limits _ {k=1} ^ {n-1}(d_k + 1) + \sum \limits _ {j=2} ^ {n-1} \prod \limits _ {k=j} ^ {n-1}(d_k + 1) \\
&= {\scriptsize (d_1 + 1) ((d_1 + 1) + 1) ^ {(n - 1 - m') - 2 + 1} \cdot ((d_1 + 2) + 1) ^ {(n - 1) - (n - m') + 1} + \sum \limits _ {j=2} ^ {n-1} \prod \limits _ {k=j} ^ {n-1}(d_k + 1) } \\
&= {\scriptsize (d_1 + 1) (d_1 + 2) ^ {n - m' - 2} (d_1 + 3) ^ {m'} + \sum \limits _ {j=2} ^ {n-1} \prod \limits _ {k=j} ^ {n-1}(d_k + 1) } \\
&= {\scriptsize (d_1 + 1) (d_1 + 2) ^ {n - m' - 2} (d_1 + 3) ^ {m'} + \sum \limits _ {j=2} ^ {n-1-m'} \prod \limits _ {k=j} ^ {n-1}(d_k + 1) + \sum \limits _ {j=n-m'} ^ {n-1} \prod \limits _ {k=j} ^ {n-1}(d_k + 1) } \\
&= {\tiny (d_1 + 1) (d_1 + 2) ^ {n - m' - 2} (d_1 + 3) ^ {m'} + \sum \limits _ {j=2} ^ {n-1-m'} \left((d_1 + 2) ^ {(n-1-m') - j + 1} \cdot (d_1 + 3) ^ {m'} \right) + \sum \limits _ {j=n-m'} ^ {n-1} \prod \limits _ {k=j} ^ {n-1}(d_k + 1) } \\
&= {\tiny (d_1 + 1) (d_1 + 2) ^ {n - m' - 2} (d_1 + 3) ^ {m'} + (d_1 + 3) ^ {m'} \cdot \sum \limits _ {j=2} ^ {n-1-m'} (d_1 + 2) ^ {(n-1-m') - j + 1} + \sum \limits _ {j=n-m'} ^ {n-1} \prod \limits _ {k=j} ^ {n-1}(d_k + 1) } \\
&= {\tiny (d_1 + 1) (d_1 + 2) ^ {n - m' - 2} (d_1 + 3) ^ {m'} + (d_1 + 3) ^ {m'} \cdot \sum \limits _ {j=1} ^ {(n-1-m') - 2 + 1} (d_1 + 2) ^ j + \sum \limits _ {j=n-m'} ^ {n-1} \prod \limits _ {k=j} ^ {n-1}(d_k + 1) } \\
&= {\tiny (d_1 + 1) (d_1 + 2) ^ {n - m' - 2} (d_1 + 3) ^ {m'} + (d_1 + 3) ^ {m'} \cfrac{(d_1 + 2) ^ {n - 1 - m'} - (d_1 + 2)}{d_1 + 1} + \sum \limits _ {j=n-m'} ^ {n-1} \prod \limits _ {k=j} ^ {n-1}(d_k + 1) } \\
&= {\tiny (d_1 + 1) (d_1 + 2) ^ {n - m' - 2} (d_1 + 3) ^ {m'} + (d_1 + 3) ^ {m'} \cfrac{(d_1 + 2) ^ {n - 1 - m'} - (d_1 + 2)}{d_1 + 1} + \sum \limits _ {j=n-m'} ^ {n-1} \prod \limits _ {k=j} ^ {n-1}(d_1 + 3) } \\
&= {\tiny (d_1 + 1) (d_1 + 2) ^ {n - m' - 2} (d_1 + 3) ^ {m'} + (d_1 + 3) ^ {m'} \cfrac{(d_1 + 2) ^ {n - 1 - m'} - (d_1 + 2)}{d_1 + 1} + \sum \limits _ {j=n-m'} ^ {n-1} (d_1 + 3) ^ {n-j} } \\
&= {\tiny (d_1 + 1) (d_1 + 2) ^ {n - m' - 2} (d_1 + 3) ^ {m'} + (d_1 + 3) ^ {m'} \cfrac{(d_1 + 2) ^ {n - 1 - m'} - (d_1 + 2)}{d_1 + 1} + \sum \limits _ {j=1} ^ {m'} (d_1 + 3) ^ j } \\
&= {\tiny (d_1 + 1) (d_1 + 2) ^ {n - m' - 2} (d_1 + 3) ^ {m'} + (d_1 + 3) ^ {m'} \cfrac{(d_1 + 2) ^ {n - 1 - m'} - (d_1 + 2)}{d_1 + 1} + \cfrac{(d_1 + 3) ^ {m' + 1} - (d1 + 3)}{d_1 + 2} }
\end{aligned}
其中，d_1 和 m' 在上文已经算出，故该式可以在 \Theta(\log m) 的时间内算出。
代码
注意特判 n = 1 的情况。
def fpow(a, b, mod):
if b < 0:
return 1
res = 1
base = a % mod
while b:
if b & 1:
res = res * base % mod
base = base * base % mod
b >>= 1
return res
def inv(x, mod):
return fpow(x, mod - 2, mod)
def main():
n, m, mod = map(int, input().split())
if n == 1:
print(0)
return
if m < n - 1:
pr = fpow(2, m, mod)
print((pr * (n - m + 1) + mod - 2) % mod)
return
d1 = (m - (n - 2)) // (n - 1)
M = m - (n - 2) - (n - 1) * d1
S1 = (d1 + 1) * fpow(d1 + 2, n - M - 2, mod) * fpow(d1 + 3, M, mod)
S2 = fpow(d1 + 3, M, mod) * (fpow(d1 + 2, n - 1 - M, mod) - (d1 + 2) + mod) * inv(d1 + 1, mod)
S3 = (fpow(d1 + 3, M + 1, mod) - (d1 + 3) + mod) * inv(d1 + 2, mod)
S1 %= mod
S2 %= mod
S3 %= mod
print((S1 + S2 + S3) % mod)
if __name__ == '__main__':
t = int(input())
for i in range(t):
main()后记
用 python 写的目的是因为教练讲题时用 python 打表唤起了我的回忆？