题意简述
小 \(G\) 参加了一次考试,一共有 \(n\) 题,每题一分。第 \(i\) 道题有 \(a_i\) 个选项,小 \(G\) 原定每道题随机选择一个选项,但是她写在答题卡上时,第 \(i\) 题的答案抄到了第 \(i+1\) 题上(第 \(n\) 题抄到了第一题),问小 \(G\) 的期望得分,保留三位小数。
\(1 \leq n \leq 10^7,1 \leq a_i \leq 10^8\)。
Solution
考虑第 \(i\) 题得分的期望,最后总的期望得分就是每一题的期望得分的和,设上一题的选项有 \(last\) 个。
- 若 \(last>a_i\) ,则要先选中选项,概率为 \(\dfrac{a_i}{last}\) ,再从 \(a_i\) 个选项中选出正确答案概率是, \(\dfrac{1}{a_i}\) ,期望为 \(\dfrac{a_i}{last} \times \dfrac{1}{a_i} \times 1 = \dfrac{1}{last}\)。
- 若 \(last < a_i\) ,那么正确答案要是 \(1\sim last\) 中的一个才有可能选对,概率是 \(\dfrac{last}{a_i}\) ,再从 \(last\) 选项中选出正确答案,概率是 \(\dfrac{1}{last}\)。期望为 \(\dfrac{last}{a_i} \times \dfrac{1}{last} \times 1=\dfrac{1}{a_i}\)。
综上,每一题得分的期望为 \(\dfrac{1}{\max\{last,a_i\}}\),答案就全部加起来就可以了。
代码如下:
#include <cstdio>
#include <cstring>
#include <cctype>
#include <algorithm>
#include <iostream>
#include <queue>
using namespace std;
const int N = 1e7 + 5;
int n ,A ,B ,C ,a[N]; double ans;
signed 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 += (double)1.0 / max(a[i] ,a[i + 1]);
ans += (double)1.0 / max(a[n] ,a[1]);
printf("%.3f\n" ,ans);
return 0;
}