[BZOJ 2134]单选错位

Description

题库链接

共有 (n) 道单选题，第 (i) 道单选题有 (a_i) 个选项，这 (a_i) 个选项编号是 (1,2,3,…,a_i)，每个选项成为正确答案的概率都是相等的。你把答案抄到答题纸上，没想到抄错位了：第 (i) 道题目的答案抄到了答题纸上的第 (i+1) 道题目的位置上，特别地，第 (n) 道题目的答案抄到了第 (1) 道题目的位置上。假设你没有做错任何题目，只是答案抄错位置，求期望能做对几道题目。

(2leq nleq 10000000,1leq a_ileq 100000000)

Solution

假设第 (i) 道题有 (x) 个选项，第 (i+1) 题有 (y) 个选项。

1. (x=y)，显然此时做对第 (i+1) 题的概率 (p=frac{1}{x}=frac{1}{y})；
2. (x>y)，由条件概率的思想，做对第 (i+1) 题的概率为第 (i) 题的选项在 (i+1) 题中可行的前提下，在 (i+1) 题中正确的概率，那么 (p=frac{y}{x} imesfrac{1}{y}=frac{1}{x})；
3. (x<y)，同理，做对第 (i+1) 题的概率为第 (i+1) 题的正确选项在 (i) 题中可行时选中的概率，那么 (p=frac{x}{y} imesfrac{1}{x}=frac{1}{y})。

综上，做对第 (i+1) 题的概率为 (p=frac{1}{max{a_{i},a_{i+1}}})。

Code

#include <bits/stdc++.h>
using namespace std;
const int N = 10000000+5;

int n, A, B, C, a[N];
double ans;

int main() {
    scanf("%d%d%d%d%d", &n, &A, &B, &C, a+1);
    for (int i = 2; i <= n; i++)
        a[i] = (1ll*a[i-1]*A+B)%100000001;
    for (int i = 1; i <= n; i++)
        a[i] = a[i]%C+1;
    for (int i = 2; i <= n; i++)
        ans += 1./max(a[i], a[i-1]);
    ans += 1./max(a[n], a[1]);
    printf("%.3lf
", ans);
    return 0;
}