洛谷 P8989 [北大集训 2021] 随机游走题解

XuYueming / 2024-04-25 / 原文

前言

~~又是随机游走？~~

题目分析

看到加边，可能性太多了。但是为了让步数最大化，我们可以贪心地想，肯定要往前面连，而且越前面要走的期望步数肯定越大。并且，我们不会浪费边在终点上。于是，题目转变成了 $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 \\ =& \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 \\ =& \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 \\ =& \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 + \cfrac{(d_{n-3} + 1) \cdot (d_{n-2}+1) + (d_{n - 2} + 1) + 1}{(d_{n-3} + 1) \cdot (d_{n-2}+1)} \\ =& \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 &= \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 \\ &= \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 \\ &= \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)} \]

解方程。

\[ \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$ 更大。

其次……没其次了，打表吧。

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$，如此往复，像是在不断从右往左往序列上刷。感性理解，具体证明交给读者。

那么，我们分别考虑两种情况即可。

情况一

当 $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} \large 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) \\ &= (d_1 + 1) \cdot ((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) \\ &= (d_1 + 1) \cdot (d_1 + 2) ^ {n - m' - 2} \cdot (d_1 + 3) ^ {m'} + \sum \limits _ {j=2} ^ {n-1} \prod \limits _ {k=j} ^ {n-1}(d_k + 1) \\ &= (d_1 + 1) \cdot (d_1 + 2) ^ {n - m' - 2} \cdot (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) \\ &= (d_1 + 1) \cdot (d_1 + 2) ^ {n - m' - 2} \cdot (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) \\ &= (d_1 + 1) \cdot (d_1 + 2) ^ {n - m' - 2} \cdot (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) \\ &= (d_1 + 1) \cdot (d_1 + 2) ^ {n - m' - 2} \cdot (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) \\ &= (d_1 + 1) \cdot (d_1 + 2) ^ {n - m' - 2} \cdot (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) \\ &= (d_1 + 1) \cdot (d_1 + 2) ^ {n - m' - 2} \cdot (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) \\ &= (d_1 + 1) \cdot (d_1 + 2) ^ {n - m' - 2} \cdot (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} \\ &= (d_1 + 1) \cdot (d_1 + 2) ^ {n - m' - 2} \cdot (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 \\ &= (d_1 + 1) \cdot (d_1 + 2) ^ {n - m' - 2} \cdot (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()