Luogu_P1297 [国家集训队]单选错位 概率期望

Luogu_P1297 [国家集训队]单选错位

### 期望

题目链接
虽然是期望，但是每个贡献都是\(1\)所以也就是概率
\(a_i\)和\(a_{i+1}\)要分类讨论
如果\(a_i=a_{i+1}\)那么明显概率就是\(\frac{1}{a_i}=\frac{1}{a_i+1}\)
如果\(a_i>a_{i+1}\)那么只有\(\frac{a_{i+1}}{a_i}\)的概率可能有用，那答对的概率就是\(\frac{a_{i+1}}{a_i}*\frac{1}{a_{i+1}}=\frac{1}{a_i}\)
如果\(a_i<a_{i+1}\)那么\(a_i\)的全部都可能有用，可用概率为\(1\)，但是答对的概率是\(1*\frac{1}{a_{i+1}}=\frac{1}{a_{i+1}}\)
我们把这三个合并起来
就是\(ans=\sum^{n}_{i=1}\frac{1}{max(a_i,a_{i+1})}\)
可以把\(1\)或者\(n\)判掉

---

代码如下：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=1e7+10;
ll a[maxn];
int n,A,B,C;
double ans=0;
int main()
{
    scanf("%d%d%d%d%d",&n,&A,&B,&C,a+1);
    for(int i=2;i<=n;i++) a[i]=((long long)a[i-1]*A+B)%100000001;
    for(int i=1;i<=n;i++) a[i]=a[i]%C+1;
    ans+=(double)1.0/max(a[1],a[n]);
    for(int i=2;i<=n;i++){
        ans+=(double)1.0/max(a[i],a[i-1]);
    }
    printf("%.3lf",ans);
    return 0;
}