BZOJ2134 单选错位

2015.01.20 09:29 Tue| 4 visits oi_2015| 2015_刷题日常| Text

Solution

对于相邻的两道题,若 $a_{i+1} \ge a_i$ ,则第 $i+1$ 题答对的概率是 ${1\over a_{i+1}}$,否则概率是 ${a_{i+1}\over a_i} \times {1\over a_{i+1}}$ 。综上,答案为 $\sum\limits_{i=1}^n \min {1\over a_i}, {1\over a_{i+1}}$ 。

Code

#include <bits/stdc++.h>
using namespace std;

#define N 10000005

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

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 ans = 0;
    a[n + 1] = a[1];
    for (int i = 1; i <= n; ++i)
        ans += min(1.0 / a[i], 1.0 / a[i + 1]);
    cout << fixed << setprecision(3) << ans << endl;
}