现有一排方块，依次编号为 1…n1\ldots n1…n。
方块 111 上有一个小人，已知当小人在方块 iii 上时，下一秒它会等概率地到方块 iii（即不动），方块 i+1i+1i+1，方块 i+2i+2i+2……方块 nnn 上。
求小人到达方块 nnn 所需要的期望时间（单位：秒）。
一个数字 nnn。
若答案 ans=ABans=\frac{A}{B}ans=?B??A?? 输出 A×B−1mod(109+7)。其中 B−1B^{-1}B?−1?? 表示 Bmod(109+7) 下的逆元。
1010000000406018741对于 50%50\%50% 的数据，n?106n \leqslant 10^6n?10?6??。
对于 100%100\%100% 的数据，1?n?1071 \leqslant n \leqslant 10^71?n?10?7??。
#include<iostream> #include<cstdio> #include<cstring> #define maxn 10000010 #define mod 1000000007 using namespace std; int inv[maxn],n; int main(){ scanf("%d",&n); inv[0]=inv[1]=1; for(int i=2;i<=n;i++) inv[i]=1LL*(mod-mod/i)*inv[mod%i]%mod; int x=0,y; for(int i=2;i<=n;i++){ y=1LL*(inv[i]+1LL*inv[i]*(x+i-1)%mod)%mod*inv[i-1]%mod*i%mod; x=(x+y)%mod; } printf("%d",y); return 0; }
原文：https://www.cnblogs.com/thmyl/p/8992386.html