自动搬运

查看原文

来自洛谷，原作者为

	stoorz **

搬运于2025-08-24 21:23:29，当前版本为作者最后更新于2019-07-04 21:45:38，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

$Blog$

分类讨论一下。

• 当$a_i=a_{i+1}$，那么显然随机的答案在第$i+1$题也是随机的。期望为$\frac{1}{a_i}$，也就是$\frac{1}{a_{i+1}}$

• 当$a_i>a_{i+1}$，只有$\frac{a_{i+1}}{a_i}$的概率答案在$1\sim a_{i+1}$中。所以期望为$\frac{a_{i+1}}{a_i}\times \frac{1}{a_{i+1}}=\frac{1}{a_i}$

• 当$a_i<a_{i+1}$，由于随机的答案只在$1\sim a_i$中，而第$i+1$题正确答案有$\frac{a_i}{a_{i+1}}$的概率在$1\sim a_i$中，所以期望为$\frac{a_i}{a_{i+1}}\times \frac{1}{a_i}=\frac{1}{a_{i+1}}$

综上，答案就是$\sum^{n}_{i=1}\frac{1}{max(a_i,a_{i+1})}$

#include <cstdio>
#include <iostream>
using namespace std;

const int N=10000010;
int n,a[N];
double ans;

void init()  //题目给出的生成数据的方法
{
	int A,B,C;
	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;
}

int main()
{
	init();
	a[n+1]=a[1];  //第1题写第n题的答案
	for (int i=1;i<=n;i++)
		ans+=1/(double)max(a[i],a[i+1]);
	printf("%0.3lf",ans);
	return 0; 
}