洛谷P1297 [国家集训队]单选错位 题解

题目链接：P1297 [国家集训队]单选错位

题意：

gx 和 lc 去参加 noip 初赛，其中有一种题型叫单项选择题，顾名思义，只有一个选项是正确答案。

试卷上共有 $n$ 道单选题，第 $i$ 道单选题有 $a_i$ 个选项，这 $a_i$ 个选项编号是 $1,2,3,\ldots,a_i$，每个选项成为正确答案的概率都是相等的。

lc 采取的策略是每道题目随机写上 $1 \sim a_i$ 的某个数作为答案选项，他用不了多少时间就能期望做对 $\sum_{i=1}^n \frac{1}{a_i}$ 道题目。gx 则是认认真真地做完了这 $n$ 道题目，可是等他做完的时候时间也所剩无几了，于是他匆忙地把答案抄到答题纸上，没想到抄错位了：第 $i$ 道题目的答案抄到了答题纸上的第 $i+1$ 道题目的位置上，特别地，第 $n$ 道题目的答案抄到了第 $1$ 道题目的位置上。

现在 gx 已经走出考场没法改了，不过他还是想知道自己期望能做对几道题目，这样他就知道会不会被 lc 鄙视了。

我们假设 gx 没有做错任何题目，只是答案抄错位置了。

输入格式：

$n$ 很大，为了避免读入耗时太多，输入文件只有 $5$ 个整数参数 $n, A, B, C, a_1$，由上交的程序产生数列 $a$。下面给出 C/C++ 的读入语句和产生序列的语句（默认从标准输入读入）：

// for C/C++
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;

选手可以通过以上的程序语句得到 $n$ 和数列 $a$（$a$ 的元素类型是 $32$ 位整数），$n$ 和 $a$ 的含义见题目描述。

输出格式：

输出一个实数，表示 gx 期望做对的题目个数，保留三位小数。

对于 $100\%$ 的数据，$2\leq n\leq 10^7, 0\leq A,B,C \leq 10^8$，$1 \leq a_i \leq 10^8$。

简单的概率题。稍微分讨一下就好了。

• 当 $a_i = a_{i+1}$ 时，期望为 $\frac{1}{a_i} = \frac{1}{a_{i+1}}$
• 当 $a_i > a_{i+1}$ 时，期望为 $\frac{a_{i+1}}{a_i}\times\frac{1}{a_{i+1}} = \frac{1}{a_i}$
• 当 $a_i < a_{i+1}$ 是，期望为 $\frac{a_i}{a_{i+1}} \times \frac{1}{a_i}=\frac{1}{a_{i+1}}$

所以答案其实就是 $\sum \frac{1}{\max\{a_{i},a_{i+1}\}}$

时间复杂度 $\mathcal{O}(n)$

代码：

#include <bits/stdc++.h>
using namespace std;
// #define int long long
// #define INF 0x3f3f3f3f3f3f3f3f
typedef long long ll;
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(1e7+15))

double res; int n,A,B,C,a[N];
void gen()
{
    cin >> n >> A >> B >> C >> a[1];
    for(int i=2; i<=n; i++)
        a[i] = ((ll)a[i - 1] * A + B) % 100000001;
    for(int i=1; i<=n; i++) a[i] = a[i] % C + 1;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cout << fixed << setprecision(3);
    gen(); res = 1.0 / (max(a[1], a[n]));
    for(int i=2; i<=n; i++)
        res += 1.0 / (max(a[i], a[i-1]));
    cout << res << '\n';
    return 0;
}