Description：

第 $i$ 个位置有 $a_i$ 个选项，各个选项出现的概率随机，假设所有题都答对但是抄错了一位，问最终得分的期望。

$1\leqslant n \leqslant 10^7$

Solution：

答案就是： $$ \sum_{i=1}^n 1\times p_{i和上一个位置答案相同} $$ 问题是 $p_i$ 怎么求，发现如果他们相同，两个选项都必定在 $[1,\min(a_i,a_{prei})]$ 中这个概率是 $\frac k{a[i]}\times \frac k{a[prei]}$ ，他们要相同，不妨先固定一个是 $x$ ，那么另一个有 $\frac 1 k$ 的概率与之相同，所以最后答案就是： $$ \sum_{i=1}^n\frac k{a[i]\times a[prei]} $$

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

#define MAXN 10000010

int n,A,B,C;

int a[MAXN];

#define prei ((i - 1 + n - 1) % n + 1)

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;

	double res = 0;

	for(int i = 1;i <= n;++i)

	{

		int k = min(a[i],a[prei]);

		res += (double)k / a[i] / a[prei];

	}

	printf("%.3lf\n",res);

	return 0;

}