Description

gx 和 lc 去参加 NOIP 初赛, 其中有一种题型叫单项选择题, 顾名思义, 只有一个选项 是正确答案. 试卷上共有 \(n\) 道单选题, 第 \(i\) 道单选题有 \(a_i\) 个选项, 这 \(a_i\) 个选项编号是 \(1, 2, 3, \ldots, a_i\), 每个选项成为正确答案的概率都是相等的. lc 采取的策略是每道题目随机写上 \(1 - a_i\) 的某个数作为答案选项, 他用不了多少时间就能 期望做对 \(\sum_{i=1}^{n} \frac{1}{a_i}\) 道题目. gx 则是认认真真地做完了这 \(n\) 道题目, 可是等他做完的时候时间也所剩无几了. 于是他匆忙地把答案抄到答题纸上, 没想 抄错位了, 第 \(i\) 道题目的答案抄到了答题纸的第 \(i+1\) 道题目的位置上, 特别地, 第 \(n\) 道题目的答案抄到了第 \(1\) 道题目的位置上. 现在 gx 已经走出考场没法改了, 不过 他还是想知道自己期望能做对几道题目, 这样他就知道会不会被 lc 鄙视了.

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

Input

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

// For C/C++ Contestants
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\) 的含义见题目描述.

Output

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

Sample Input

3 2 0 4 1

Sample Output

1.167

Data Range

对于 100% 的数据, 满足:\(2 \leq n \leq 10^7, 0 \leq A, B, C, a_1 \leq 10^8\)

Explanation

显然这道题就是一道非常傻逼的期望 DP......

考虑这一次会不会做错, 当然取决于上一次的选择了...... 所以连瞎搞都不用, 直接随便 一写就能过掉~

记住之前的期望就可以了.

Source Code


#include <iostream>
#include <cstdlib>
#include <cstdio>

using namespace std;
typedef long long lli;
typedef long double llf;
const int maxn = 100010000;
const int modr = 100000001;

int n;
lli A, B, C, a;

int main(int argc, char** argv)
{
    scanf("%d%lld%lld%lld%lld", &n, &A, &B, &C, &a);
    lli cur = a, last = a, begin = a;
    llf res = 0.0;
    for (int i = 1; i < n; i++) {
        cur = (cur * A + B) % modr;
        res += 1.0 / max(cur % C + 1, last % C + 1);
        last = cur;
    }
    res += 1.0 / max(begin % C + 1, cur % C + 1);
    printf("%.3Lf\n", res);
    return 0;
}