$n \leqslant 10^5$
随便推一推就好了吧。。
$f[i] = \frac{f[i] + f[i +1] + \dots f[n]}{n - i + 1} + 1$
移一下项,然后化一化,就做完了。。
然而这题卡空间MMP
#include<cstdio>
#include<algorithm>
#include<iostream>
//#define int long long
#define Pair pair<int, int>
#define fi first
#define se second
#define MP(x, y) make_pair(x, y)
using namespace std;
const int MAXN = 1e7 + 10, INF = 1e9 + 10, mod = 1e9 + 7;
inline int read() {
char c = getchar(); int x = 0, f = 1;
while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
return x * f;
}
int N;
int inv[MAXN];
main() {
N = read();
int s = 0, now = 0;
inv[1] = 1;
for(int i = 2; i <= N; i++) inv[i] = 1ll * (mod - mod / i) * inv[mod % i] % mod;
for(int i = N - 1; i >= 1; i--) {
now = 1ll * (s + N - i + 1) * inv[N - i] % mod;
s = (s + now) % mod;
}
cout << (now + mod) % mod;
return 0;
}
/*
10000000
*/