洛谷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;
}