题目大意

给定一条从 $1$ 到 $n$ 的链（$i \to i+1$），可以添加 $m$ 条有向边（任意起点终点，允许重边自环）。从 $1$ 出发随机游走到 $n$，求通过最优加边策略能获得的最大期望步数对质数 $p$ 取模的结果。

数据范围：$n, m \leq 10^{18}$，$T \leq 10^5$

核心思路

1. 最优策略分析

通过数学推导发现，最优策略是：

• 在除了点 $n-1$ 和点 $n$ 之外的其他点上，尽可能多地添加指向点 $1$ 的边
• 这样能最大化被困在前面的循环中的概率，从而增加期望步数

2. 数学公式推导

设 $k = \lfloor \frac{m}{n-1} \rfloor$，$r = m \bmod (n-1)$

经过推导，最大期望步数的闭式解为：

情况1：当 $r = n-2$ 或 $r = n-3$ 时

$$E = \frac{(k+2)^{r+1} - (k+1)^{n-1-r}}{k+1}$$

情况2：其他情况

$$E = \frac{(k+2)^{r+2} - (k+1)^{n-2-r}}{k+1}$$

算法实现详解

1. 关键变量定义

long long T, n, m, p, ans, t[2], q[2];

• t[0], t[1]：用于快速幂计算的临时变量
• q[0], q[1]：平方递推的中间结果

2. 特殊情况处理

if (n == 1) {
    printf("0\n");
    continue;
}

当 $n=1$ 时，起点就是终点，期望步数为 $0$。

3. 分类计算框架

if (m <= n - 2 || m % (n - 1) == n - 2 || m % (n - 1) == n - 3) {
    // 情况1：使用公式 E = ((k+2)^(r+1) - (k+1)^(n-1-r)) / (k+1)
} else {
    // 情况2：使用公式 E = ((k+2)^(r+2) - (k+1)^(n-2-r)) / (k+1)
}

4. 快速幂计算核心

算法采用二进制分解的快速幂方法：

// 计算 base^exp 的快速幂
t[0] = base % p;
t[1] = base % p;
ans = 0;

for (i = 0; i <= 30; i++) {
    if (exp & (1 << i))
        ans = (ans * t[0] + t[1]) % p;
    
    // 平方递推
    q[0] = t[0] * t[0] % p;
    q[1] = (t[1] * t[0] + t[1]) % p;
    t[0] = q[0];
    t[1] = q[1];
}

技术细节：

• 使用 t[0] 和 t[1] 同时维护幂次和部分和
• 通过30次循环覆盖 $2^{30} > 10^9$ 的指数范围
• 每次迭代进行平方操作，实现对数复杂度

5. 具体计算步骤

情况1计算：

// 计算 (k+1)^(n-1-r)
t[0] = (k + 1) % p;  // k = m/(n-1)
ans = 0;
for (i = 0; i <= 30; i++) {
    if ((n-1-r) & (1 << i))
        ans = (ans * t[0] + t[1]) % p;
    // 平方递推...
}

// 计算 (k+2)^(r+1) 并组合结果
t[0] = (k + 2) % p;
// ...类似处理

情况2计算：

类似但指数不同，对应推导出的另一种公式形式。

关键优化

1. 快速幂优化

• 使用二进制分解将指数运算从 $O(n)$ 优化到 $O(\log n)$
• 适合处理 $n \leq 10^{18}$ 的超大范围

2. 模运算优化

• 及时取模避免溢出
• 利用质数模数的性质

3. 分类讨论优化

• 根据 $r$ 的不同值采用不同公式
• 避免不必要的计算

复杂度分析

• 预处理：$O(1)$，只有常数时间计算
• 快速幂：$O(\log n)$，每个测试用例30次循环
• 总复杂度：$O(T \log n)$，适合 $T \leq 10^5$ 的数据范围

算法标签

主要算法：

• 数学推导
• 快速幂
• 模运算

数学工具：

• 期望计算
• 组合优化
• 闭式解推导

优化技术：

• 二进制分解
• 分类讨论
• 常数优化

代码亮点

1. 数学洞察：将复杂的期望最大化问题转化为简洁的闭式解
2. 高效实现：使用快速幂处理超大指数运算
3. 边界完善：正确处理 $n=1$ 等边界情况
4. 模运算安全：精心设计避免中间结果溢出

总结

这道题通过深入的数学分析，发现了期望步数最大化的最优策略和闭式表达式。算法核心在于高效计算模意义下的幂运算，通过快速幂技术在对数时间内解决问题。这种"数学推导+高效实现"的解题思路在竞赛中非常典型，体现了对问题本质的深刻理解和算法优化能力。