P1297 [国家集训队]单选错位 【期望】

https://www.luogu.com.cn/problem/P1297

考虑期望的线性性。E(x + y + z) = E(x) + E(y) + E(z)
跟x，y，z独立性无关`

E(i)：表示第i个题正确的期望，这里也就是概率 * 1，所以跟概率是相等的。
E(i) = min(a[i-1),a[i])/(a[i-1] * a[i])
(a[i-1] * a[i]): 表示所有的情况数
min(a[i-1),a[i])：表示两个题答案一一对应的情况数

#include <stdio.h>
#include <cstring>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <iostream>
#include <map>

#define go(i, l, r) for(int i = (l), i##end = (int)(r); i <= i##end; ++i)
#define god(i, r, l) for(int i = (r), i##end = (int)(l); i >= i##end; --i)
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define debug_in  freopen("in.txt","r",stdin)
#define debug_out freopen("out.txt","w",stdout);
#define pb push_back
#define all(x) x.begin(),x.end()
#define fs first
#define sc second
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> pii;
const ll maxn = 1e7+10;
const ll maxM = 1e6+10;
const ll inf_int = 1e8;
const ll inf_ll = 1e17;

template<class T>void read(T &x){
    T s=0,w=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
    x = s*w;
}
template<class H, class... T> void read(H& h, T&... t) {
    read(h);
    read(t...);
}

void pt(){ cout<<'\n';}
template<class H, class ... T> void pt(H h,T... t){ cout<<" "<<h; pt(t...);}

//--------------------------------------------

int n,A,B,C;
int a[maxn];
void solve(){
    double ans = 0;
    a[n+1] = a[1];
    go(i,2,n+1){
        ans += min(a[i-1],a[i])/((double)a[i-1] * a[i]);
    }
    printf("%.3f\n",ans);
}
int main() {
//    debug_in;
//    debug_out;

    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;


    solve();

    return 0;
}