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

注：本蒟蒻的第一个期望题（因为看到臭气弹所以来学习一下）

思路

对于每一个\(1\)题目，显然有：

\[\notag p_i=\frac{\min(a_i,a_{i-1})}{a_i\times a_{i-1}} \]

解释：由于抄错位了，所以选中的情况一共有\(\min(a_i,a_{i-1})\)。而\(a_i,a_{i-1}\)的组合情况一共有\(a_i\times a_{i-1}\)种，故概率如上。

当然这个公式可以约分（洛谷大佬说的）：

\[\notag 当 ~ a_i<=a_{i-1} ~ 时\\ p_i=\frac{1}{a_{i-1}}\\ 当 ~ a_i>a_{i-1} ~ 时\\ p_i=\frac{1}{a_i}\\ 综上：p_i=\frac{1}{\max(a_i,a_{i-1})} \]

CODE

#include
#define ll long long
#define ld long double
using namespace std;
const int maxn = 1e7+32;
int int_maxn=1e9;
ll ll_maxn=1e18;
inline ll read_int(){
    ll a=0,f=0,g=getchar();
    while(g<'0'||g>'9'){if(g=='-') f=1;g=getchar();}
    while('0'<=g&&g<='9') a=a*10+g-'0',g=getchar();
    return f ? -a : a;
}

inline void write(ll s,bool f){
    int top=0,a[40];
    if(s<0) s=-s,putchar('-');
    while(s) a[++top]=s%10,s/=10;
    if(top==0) a[++top]=0;
    while(top) putchar(a[top]+'0'),top--;
    if(f) putchar('\n');
}

int a[maxn];
int n,A,B,C;
ld ans;

inline void begin(){
	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;
}

inline void read(){
	n=read_int(),A=read_int(),B=read_int(),C=read_int(),*(a+1)=read_int();
	begin();
	for(int i=2;i<=n;i++){
		ans+=(ld)1/max(a[i],a[i-1]);
	}
	ans+=(ld)1/max(a[1],a[n]);
	printf("%.3Lf\n",ans);
}

int main (){
	read(); 
}