[loj 6342]跳一跳

题目链接

https://loj.ac/problem/6342

题解

某年 NOIp 初赛题。

设 \(f(i)\) 表示从 \(1\) 到 \(i\) 的期望步数。边界是 \(f(1)=0\)，当 \(i \geq 2\) 时，显然有如下递推式：

$$f(i)=1+\sum_{j=1}^{i} \frac{f_j}{n}$$

整理后可以得到：

$$f(i)=\begin{cases}0&,& i=1\\ \frac{1}{n-1}(n+\sum_{j=1}^{i-1} f_j)&,&i \geq 2\end{cases}$$

预处理逆元即可在 \(O(n)\) 的时间内解决。

#include <iostream>
#define MOD 1000000007
using namespace std;
int inv[10000005];
int main()
{
 int n;
 cin>>n;
 inv[1]=1;
 for(int i=2;i<=n;i++)
  inv[i]=1ll*(MOD-MOD/i)*inv[MOD%i]%MOD;
 long long sum=0,f=0;
 for(int i=2;i<=n;i++)
  f=(1ll*i*inv[i-1]+1ll*sum*inv[i-1])%MOD,sum=(sum+f)%MOD;
 cout<<f<<endl;
 return 0;
}