[国家集训队] 单选错位

题目大意

nn 道单选题,每道有选项 aia_i 个,每个选项成为正确答案的几率相同。今有一人答对了所有的单选题,但是第 ii 道的答案写在了第 i+1i + 1 道的位置上,特别的,第 nn 道写在了第 11 道的位置上。求其期望答对的题数。

aia_i 由以下方式生成:

1
2
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

1n,  A,  B.  C,  a110,000,0001 \leqslant n, \; A, \; B. \; C, \; a_1 \leqslant 10,000,000

题目链接

【国家集训队】单选错位 - Luogu 1297

题解

x=ai,  y=ai+1x = a_i, \; y = a_{i + 1}

x>yx > y:第 ii 道的答案有 yx\frac{y}x 的概率会有可能成为第 i+1i + 1 道的答案,又由各选项成为答案的几率相同,所以第 $i $ 道的答案填入第 i+1i + 1 道答案正确的概率是 yx×1y=1x\frac{y}x \times \frac{1}y = \frac{1}x

同理,xyx \leqslant y 时的概率为 1y\frac{1}y

综上,答案为:

i=1n1max(ai,  ai+1)(an+1=a1)\sum_{i = 1}^{n} \frac{1}{max(a_i, \; a_{i + 1})} \quad (a_{n + 1} = a_1)

代码

概率与期望入门题?概率与期望对我来说就是恐怖的存在。。。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <cstdio>
#include <algorithm>
int main() {
int n, A, B, C, a1;
scanf("%d %d %d %d %d", &n, &A, &B, &C, &a1);
int x = a1, y;
double ans = 0;
for (int i = 1; i < n; i++) {
y = ((long long) x * A + B) % 100000001;
ans += 1.0 / std::max(x % C + 1, y % C + 1);
x = y;
}
ans += 1.0 / std::max(y % C + 1, a1 % C + 1);
printf("%.3lf\n", ans);
}