方块移动期望时间问题解析

问题分析

题目描述：一排编号为1到n的方块，小人从方块1出发，移动规则为：当在方块i上时，下一秒会等概率移动到方块i、i+1、……、n中的任意一个。求到达方块n的期望时间（单位：秒），结果以分数A/B的形式表示为A×B⁻¹ mod (10⁹+7)。

递推公式推导

设E[i]为从方块i到达方块n的期望时间。显然，E[n] = 0（已到达目标）。

对于i < n时，分析移动规则：

• 从方块i出发，可移动到i、i+1、……、n，共k = n - i + 1个位置
• 每个位置的概率为1/k
• 期望时间满足：E[i] = 1 + (E[i] + E[i+1] + ... + E[n])/k（1秒为当前步，加上后续期望的平均值）

整理方程： 两边乘以k得：k·E[i] = k + E[i] + E[i+1] + ... + E[n] 移项化简：(k-1)·E[i] = k + (E[i+1] + ... + E[n]) 其中k = n - i + 1，故k-1 = n - i，代入得： E[i] = [ (n - i + 1) + (E[i+1] + ... + E[n]) ] / (n - i)

优化计算与递推

直接计算E[i]需累加E[i+1]到E[n]，时间复杂度会达O(n²)，不适合n=1e7的规模。引入辅助变量S[i] = E[i] + E[i+1] + ... + E[n]（从i到n的期望和），则：

• S[i] = E[i] + S[i+1]
• E[i]的表达式可改写为：E[i] = [ (n - i + 1) + S[i+1] ] / (n - i)

利用S[i]的递推关系，可将计算优化为O(n)：

• 从i = n-1逆推至i = 1（因E[n] = 0，S[n] = 0）
• 每次计算E[i]时，S[i+1]已通过之前的结果累加得到

模运算与逆元处理

结果需以A×B⁻¹ mod (10⁹+7)表示，其中B⁻¹是B在模10⁹+7下的乘法逆元。由于计算E[i]时涉及除法（除以n-i），需用逆元替代：

• 逆元计算采用线性递推公式：inv[1] = 1；对于i > 1，inv[i] = MOD - MOD/i × inv[MOD%i] % MOD（MOD=1e9+7）
• 该方法可在O(n)时间内预处理1到n的所有逆元

代码解析

#include <iostream>
using namespace std;
typedef long long ll;
ll n;
ll ans;
const ll MOD = 1e9 + 7, MAXN = 1e7;
ll dp = 0, s = 0;  // dp表示E[i]，s表示S[i+1]（E[i+1]到E[n]的和）
int inv[MAXN + 10];  // 逆元数组

int main() {
    ios::sync_with_stdio(0);
    cin >> n;
    if (n == 1) {  // 特殊情况：已在目标位置
        cout << 0;
        return 0;
    }
    // 预处理逆元
    inv[1] = 1;
    for (int i = 2; i <= n; i++)
        inv[i] = MOD - MOD / i * inv[MOD % i] % MOD;
    
    // 从i = n-1逆推到i = 1
    for (ll i = n - 1; i > 0; i--) {
        s = (s + dp) % MOD;  // 更新S[i+1]（累加E[i+1]）
        ll k_minus_1 = n - i;  // k-1 = n - i
        ll numerator = (s + (n - i + 1)) % MOD;  // 分子：(n-i+1) + S[i+1]
        dp = numerator * inv[k_minus_1] % MOD;  // E[i] = 分子 / (n-i) = 分子 × 逆元
    }
    
    cout << dp;  // dp最终为E[1]
}

时间复杂度分析

• 逆元预处理：O(n)
• 递推计算E[i]：O(n)
• 总时间复杂度：O(n)，可高效处理n=1e7的规模。