抽象场。打完人自闭的那种。
得分情况：\(80-0-30-30\)。
A：从 \(0\) 走到 \(n\)。在 \(i\) 位置时，等概率走的走到 \([i+1,n]\)（视为一步）。求期望步数。
哥们赛时，爆搜打表找规律。。。最后写的 O(n)，没看到第九个数据点没有特判。对于最后一个点 1e18，递推式写出来但不会进一步求。遗憾离场。
以下是正确的推导过程。
另 \(f[i]\) 表示走到 \(i\) 时的期望步数。\(0<j<i-1\)，让 \(i\) 从 \(j\) 转移过来，每种可能都为 \(1/i\)，最后加上转移的这一步。得到 o(n^2) 的暴力 dp。
#include<bits/stdc++.h>
#define db double
using namespace std;
const int N=1e7+10;
int n;
db f[N];
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
for(int j=0;j<i;j++) f[i]+=f[j];
f[i]=f[i]/i+1;
}
printf("%.6lf",f[n]);
}
加上前缀和优化，得到 \(O(n)\)。
#include<bits/stdc++.h>
#define db double
using namespace std;
const int N=1e7+10;
int n;
db f[N],sum;
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
f[i]=sum/i+1;
sum+=f[i];
}
printf("%.6lf",f[n]);
}
这就 80pts。然后打表特判第九个点。数组存不下，直接用变量。
考虑最后 \(n<=1e18\)，肯定有什么规律。大胆猜想：\(f_i=\sum_{i=1}^n{\frac{1}{i}}\)。
然后证明：
\(dp_i={\frac{1}{i}}(\displaystyle\sum_{j=0}^{i-1}dp_j+1\)
\(=\frac{1}{i}(\displaystyle\sum_{j=0}^{i-2}dp_j+dp_{i-1})+1\)
\(=\frac{1}{i}(\displaystyle\sum_{j=0}^{i-2}dp_j+(\frac{1}{i-1}(\displaystyle\sum_{j=0}^{i-2}dp_j)+1))+1\)
\(=\frac{1}{i}(\frac{i}{i-1} \displaystyle\sum_{j=0}^{i=2}dp_j+1)+1\)
\(=(\frac{1}{i-1}\displaystyle\sum_{j=0}^{i-2}dp_j+1)+\frac{1}{i}\)
\(=dp_{i-1}+\frac{1}{i}\)
然后就是调和级数的计算了。调和级数是什么，我也不是很懂，只是知道这样的式子：
\(H_n=\displaystyle\sum_{i=1}^{n} \frac{1}{i}=\ln n+\gamma+\varepsilon_n\)
\(\gamma\) 为欧拉-马歇尔罗尼常数。约为 \(0.57721 56649 01532 86060 65120 90082\) 。
\(\varepsilon_n\) 约等于 \(\frac{1}{2n}\)，当 \(n \to \infty\) 时 \(\varepsilon_m \to 0\)。
因此小范围暴力，大范围输出这个。
#include<bits/stdc++.h>
#define ll long long
#define db double
using namespace std;
ll n;
db sum;
int main(){
scanf("%lld",&n);
if(n>5e8){
printf("%.6lf",log(n)+0.57721566490153286060);
return 0;
}
for(int i=1;i<=n;i++) sum+=1.0/i;
printf("%.6lf",sum);
}
注意 c++ 中 log() 默认是数学中的 ln()，以 2 为底是 lg2()，以 10 为底是 lg10()。