单选错位
[问题描述]
gx 和 lc 去参加 noip 初赛, 其中有一种题型叫单项选择题, 顾名思义, 只有一个选项是正确答案. 试卷上共有 n 道单选题, 第 i 道单选题有
ai
个选项, 这
ai
个选项编号是
1,2,3,...,ai
, 每个选项成为正确答案的概率都是相等的. lc 采取的策略是每道题目随机写上
1-ai
的某个数作为答案选项, 他用不了多少时间就能期望做对道题目. gx 则是认认真真地做完了这 n 道题目, 可是等他做完的时候时间也所剩无几了, 于是他匆忙地把答案抄到答题纸上, 没想到抄错位了: 第 i 道题目的答案抄到了答题纸上的第 i+1 道题目的位置上, 特别地, 第 n 道题目的答案抄到了第 1 道题目的位置上. 现在 gx 已经走出考场没法改了, 不过他还是想知道自己期望能做对几道题目, 这样他就知道会不会被 lc 鄙视了.
我们假设 gx 没有做错任何题目, 只是答案抄错位置了.
[输入格式]
n 很大, 为了避免读入耗时太多, 输入文件只有 5 个整数参数 n
, A, B, C, a
1
, 由上交的程序产生数列 a. 下面给出 pascal/C/C++ 的读入语句和产生序列的语句 (默认从标准输入读入):
选手可以通过以上的程序语句得到 n 和数列 a(a 的元素类型是 32 位整数),n 和 a 的含义见题目描述.
[输出格式]
- #include<iostream>
- #include<cstdio>
- #include<algorithm>
- #include<cmath>
- #include<cstring>
- using namespace std;
- template <typename tn> void read (tn & a) {
- tn x = 0, f = 1;
- char c = getchar();
- while (c <'0' || c> '9'){ if (c == '-') f = -1; c = getchar(); }
- while (c>= '0' && c <= '9'){ x = x * 10 + c - '0'; c = getchar(); }
- a = f == 1 ? x : -x;
- }
- const long long MAXN = 10000100;
- long long n, A, B, C;
- long long a[MAXN];
- double ans;
- int main() {
- read(n);
- read(A);
- read(B);
- read(C);
- read(a[1]);
- ans = 0;
- 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;
- }
- a[0] = a[n];
- for (int i = 1; i <= n; ++i) {
- ans += (double)1 / (double)(max(a[i], a[i - 1]));
- }
- printf("%.3f\n", ans);
- return 0;
- }
- View Code
来源: http://www.bubuko.com/infodetail-2566575.html