logo AlgoBeat OnlineJudge
登录 注册

#102134. [BZOJ 2134] 单选错位

内存限制：259 MiB 时间限制：10000 ms 标准输入输出
题目类型：传统 评测方式：文本比较
上传者： 匿名
提交 提交记录 统计 测试数据 讨论 题解

题目描述

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

试卷上共有 道单选题，第 道单选题有 个选项，这 个选项编号是 ，每个选项成为正确答案的概率都是相等的。

lc 采取的策略是每道题目随机写上 的某个数作为答案选项，他用不了多少时间就能期望做对 道题目。

gx 则是认认真真地做完了这 道题目，可是等他做完的时候时间也所剩无几了，于是他匆忙地把答案抄到答题纸上，没想到抄错位了：第 道题目的答案抄到了答题纸上的第 道题目的位置上，特别地，第 道题目的答案抄到了第 道题目的位置上。

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

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

输入格式

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

// for pascal
readln(n,A,B,C,q[1]);
for i:=2 to n do
q[i] := (int64(q[i-1]) * A + B) mod 100000001;
for i:=1 to n do
q[i] := q[i] mod C + 1;

// 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;

选手可以通过以上的程序语句得到 和数列 ， 和 的含义见题目描述。

输出格式

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

样例

样例输入 #1

3 2 0 4 1

样例输出 #1

1.167

样例说明

。

正确答案 gx的答案 做对题目 出现概率

共有 种情况，每种情况出现的概率是 ，gx 期望做对 题。（相比之下，lc 随机就能期望做对 题）

数据范围与提示

对于 的数据，，。

对于 的数据，，。

对于 的数据，，。

对于 的数据，，。

显示分类标签

编辑器加载中 …
Powered by SYZOJ. Modified by Zemu (UnratedCheater).
项目源码 · 陶片放逐 · 新ICP备2026003452号-2
当前版本：V1.7.2-premium