BZOJ_2134_单选错位——期望DP

BZOJ_2134_单选错位——期望DP

题意：

分析：
设A为Ai ∈ [1,ai+1] 的概率，B为Ai = A(imodn+1)的概率
显然P(A|B) = 1,那么根据贝叶斯定理P(B) = P(B|A)*P(A)
P(A) = min(ai,ai+1)/ai
P(B|A) = 1/a(i+1)
P(B) = min(ai,ai+1)/(ai*a(i+1))
又因为期望的可加性，直接加起来统计答案

代码：

#include <stdio.h>

#include <string.h>

#include <algorithm>

#include <queue>

using namespace std;

#define LL long long

#define du double

du ans;

int n,A,B,C,a[10000001];

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+=1.0/max(a[i],a[i+1]%C+1);

    a[n]=a[n]%C+1;ans+=1.0/max(a[1],a[n]);

    //for(int i=1;i<=n;i++)printf("%d\n",a[i]);

        printf("%.3lf",ans);

}