自动搬运

查看原文

来自洛谷，原作者为

	XuYueming 没拿省一不改签

搬运于2025-08-24 22:44:22，当前版本为作者最后更新于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$ 更大。

略证：

$\exists t \in [1, n-2], d_t > d_{t+1}$，考虑原先的 $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$。

证明：

$\exists t \in [1, n-2], d_t + 2 \leq d_{t+1}$，证明 $d_t \gets d_t + 1, d_{t+1} \gets d_{t+1}-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 打表唤起了我的回忆？