给一张 \(n\) 个点的有向图，初始对于 \(\forall i\in [1, n-1]\)，在 \(i\) 与 \(i+1\) 之间有一条有向边
在其中再加入 \(m\) 条有向边，允许重边和自环，最大化从 \(1\) 到 \(n\) 的期望步数
我们可以注意到几条简单的性质
- 为了尽可能最大化期望步数，所有边都会往 \(1\) 连
- 不可能从 \(n\) 连出边
设 \(\mathrm{EX}(p)\) 为从 \(p\) 出发到 \(n\) 的期望距离，点 \(p\) 连了 \(a_p\) 条边出来，那么
\[\mathrm{EX}(p)=\dfrac{1}{a_p+1}\mathrm{EX}(p+1)+\dfrac{a_p}{a_p+1}\mathrm{EX}(1)+1 \]而有 \(\mathrm{EX}(n)=0\)
\[\begin{aligned} \mathrm{EX}(n-1)&=\dfrac{a_{n-1}}{a_{n-1}+1}\mathrm{EX}(1)+1\\ \mathrm{EX}(n-2) &=\dfrac{a_{n-2}}{a_{n-2}+1}\mathrm{EX}(1) +\dfrac{1}{a_{n-2}+1}(\mathrm{EX}(n-1))+1\\ &=\dfrac{a_{n-2}}{a_{n-2}+1}\mathrm{EX}(1) +\dfrac{1}{a_{n-2}+1}(\dfrac{a_{n-1}}{a_{n-1}+1}\mathrm{EX}(1)+1)+1\\ &=\dfrac{a_{n-2}(a_{n-1}+1)+a_{n-1}}{(a_{n-2}+1)(a_{n-1}+1)}\mathrm{EX}(1)+\dfrac{a_{n-2}+2}{a_{n-2}+1} \end{aligned} \]令 \(t_k=\prod_{i=k}^{n-1}(a_i+1)\)
则
\[\begin{aligned} \mathrm{EX}(n-2) &=\dfrac{t_{n-2}-1}{t_{n-2}}\mathrm{EX}(1)+\dfrac{a_{n-2}+2}{a_{n-2}+1} \end{aligned} \]接下来
\[\begin{aligned} \mathrm{EX}(n-3) &=\dfrac{a_{n-3}}{a_{n-3}+1}\mathrm{EX}(1) +\dfrac{1}{a_{n-3}+1}(\mathrm{EX}(n-2))+1\\ &=\dfrac{a_{n-3}}{a_{n-3}+1}\mathrm{EX}(1) +\dfrac{1}{a_{n-3}+1}(\dfrac{t_{n-2}-1}{t_{n-2}}\mathrm{EX}(1)+\dfrac{a_{n-2}+2}{a_{n-2}+1})+1\\ &=\dfrac{a_{n-3}t_{n-2}+t_{n-2}-1}{t_{n-3}}\mathrm{EX}(1)+\dfrac{a_{n-2}+2+(a_{n-3}+1)(a_{n-2}+1)}{(a_{n-3}+1)(a_{n-2}+1)}\\ &=\dfrac{t_{n-3}-1}{t_{n-3}}\mathrm{EX}(1)+\dfrac{\sum_{i={n-3}}^{n-2}\frac{t_{i}}{a_{n-1}+1}+1}{\frac{t_{n-3}}{a_{n-1}+1}}\\ \mathrm{EX}(n-4) &=\dfrac{a_{n-4}}{a_{n-4}+1}\mathrm{EX}(1) +\dfrac{1}{a_{n-4}+1}(\mathrm{EX}(n-3))+1\\ &=\dfrac{a_{n-4}}{a_{n-4}+1}\mathrm{EX}(1)+\dfrac{1}{a_{n-4}+1}(\dfrac{t_{n-3}-1}{t_{n-3}}\mathrm{EX}(1)+\dfrac{\sum_{i={n-3}}^{n-2}\frac{t_{i}}{a_{n-1}+1}+1}{\frac{t_{n-3}}{a_{n-1}+1}})+1\\ &=\dfrac{t_{n-4}-1}{t_{n-4}}\mathrm{EX}(1)+\dfrac{\sum_{i=n-4}^{n-2}\frac{t_i}{a_{n-1}+1}+1}{\frac{t_{n-4}}{a_{n-1}+1}} \end{aligned} \]那么我们就有了一般的形式
\[\begin{aligned} \mathrm{EX}(k) &=\dfrac{t_k-1}{t_k}\mathrm{EX}(1)+\dfrac{\sum_{i=k}^{n-2}\frac{t_i}{a_{n-1}+1}+1}{\frac{t_k}{a_{n-1}+1}}\\ &=\dfrac{t_k-1}{t_k}\mathrm{EX}(1)+\dfrac{\sum_{i=k}^{n-2}t_i}{t_k}+\dfrac{a_{n-1}+1}{t_k}\\ \end{aligned} \]所以
\[\begin{aligned} \mathrm{EX}(1) &=\dfrac{t_1-1}{t_1}\mathrm{EX}(1)+\dfrac{\sum_{i=1}^{n-2}t_i}{t_1}+\dfrac{a_{n-1}+1}{t_1}\\ &=\sum_{i=1}^{n-2}t_i+a_{n-1}+1\\ &=\sum_{i=1}^{n-1}t_i\\ &=\sum_{i=1}^{n-1}\prod_{j=i}^{n-1}(a_j+1) \end{aligned} \]爆搜一下数列 \(a\) 就可以狂砍 \(20\rm{pts}\) 了！
现在的问题就在于最大化 \(\sum_{i=1}^{n-1}\prod_{j=i}^{n-1}(a_j+1)\)
观察可以发现在越靠后的位置，对于 \(a_i\) 对答案的贡献应该是更大的，应该尽可能大
对于 \(m < n-1\) 的情况，容易想到在 \(n-m\sim n-1\) 之间各放一个是最好的
当 \(m\ge n-1\) 的情况，整个序列分为三段，第一段为 \(a_1=\lfloor\dfrac{m-(n-2)}{n-1}\rfloor\)，第二段为 \(2\sim n-(m-a_1-(n-2)(a_1+1))-1\)，其中 \(a\) 的值为 \(a_1+1\)，最后一段是 \(n-(m-a_1-(n-2)(a_1+1))\sim n-1\)，其中 \(a\) 的值为 \(a_1+2\)
可以证明这是最优的分配方案，否则可以调整得到更优的方案
然后直接做就可以了，在相同的段内等比数列求和即可
如果一定要从小到大枚举的话可以换一下形式
\[\begin{aligned} \sum_{i=1}^{n-1}\prod_{j=i}^{n-1}(a_j+1) &=\sum_{i=1}^{n-1}\dfrac{\prod_{j=1}^{n-1}(a_j+1)}{\prod_{j=1}^{j=i-1}(a_j+1)}\\ &=\prod_{i=1}^{n-1}(a_i+1)\sum_{i=1}^{n-1}\bigg(\prod_{j=1}^{i-1}(a_j+1)\bigg)^{-1} \end{aligned} \]#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
typedef long long ll;
using namespace std;
ll n, m, mod;
ll a1, ans;
ll f_pow(ll a, ll k) {
a %= mod;
ll base = 1;
for(; k; k >>= 1, a = (a * a) % mod) {
if(k & 1)
base = (base * a) % mod;
}
return base;
}
ll Plus(ll a, ll b) {
a += b;
return a >= mod ? a - mod : a;
}
ll Minu(ll a, ll b) {
a -= b;
return a < 0 ? a + mod : a;
}
//等比数列求和,首项为a,公比为p,长度为len
ll SequenceSum(ll a, ll p, ll len) {
p %= mod;
return a % mod * Minu(1, f_pow(p, len)) % mod * f_pow(Minu(1, p), mod - 2) % mod;
}
int main() {
int T;
scanf("%d", &T);
while(T--) {
scanf("%lld%lld%lld", &n, &m, &mod);
if(m < n - 1) {
ll sum1 = SequenceSum(2, 2, m);
ll sum2 = f_pow(2, m) * (n - m - 1) % mod;
printf("%lld\n", Plus(sum1, sum2));
continue;
}
if(n == 1) {
printf("0\n");
continue;
}
a1 = (m - n + 2) / (n - 1);
ll res = m - a1 - (n - 2) * (a1 + 1);
ll mid = n - res - 1;
if(mid == 1) {
ll sum1 = SequenceSum(a1 + 3, a1 + 3, (n - 1) - 1);
ll prod = f_pow(a1 + 3, (n - 1) - 1);
ll sum2 = (a1 + 1) % mod * prod % mod;
printf("%lld\n", Plus(sum1, sum2));
} else if(mid == n - 1) {
ll sum1 = SequenceSum(a1 + 2, a1 + 2, (n - 1) - 1);
ll prod = f_pow(a1 + 2, (n - 1) - 1);
ll sum2 = (a1 + 1) % mod * prod % mod;
printf("%lld\n", Plus(sum1, sum2));
} else {
ll sum1 = SequenceSum(a1 + 3, a1 + 3, res);
ll prod1 = f_pow(a1 + 3, res);
ll sum2 = SequenceSum(prod1 * ((a1 + 2) % mod) % mod, a1 + 2, mid - 1);
ll prod2 = f_pow(a1 + 2, mid - 1);
ll sum3 = (a1 + 1) % mod * prod2 % mod * prod1 % mod;
printf("%lld\n", Plus(sum1, Plus(sum2, sum3)));
}
}
return 0;
}