BZOJ 2134 单选错位

题目大意

给你一个数列，每个数列都随机选择一个1~$a_i$的值$S_i$，求期望的$S_i=S_{i+1}$的个数。

当然是概率期望qwq

首先引入一个东西：和的期望等于概率的和。

所以这道题$S_i=S_{i+1}$的概率是$\frac{\min(a_i,a_{i+1})}{\max(a_i,a_{i+1})} \frac{1}{\min(a_i,a_{i+1})} = \frac{1}{\max(a_i,a_{i+1})}$

之后直接跑就可以了= =

#include <cstdio>
#include <algorithm>
using namespace std;
int n,A,B,C,a[10000010];
double ans;
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;
    for(int i=1;i<n;i++) ans+=1.0/max(a[i],a[i+1]);
    ans+=1.0/max(a[n],a[1]);
    printf("%.3lf\n",ans);
}