题解 P1297 【[国家集训队]单选错位】

stoorz · 2019-07-04 21:45:38 · 题解

Blog

分类讨论一下。

• 当a_i=a_{i+1}，那么显然随机的答案在第i+1题也是随机的。期望为\frac{1}{a_i}，也就是\frac{1}{a_{i+1}}

• 当a_i>a_{i+1}，只有\frac{a_{i+1}}{a_i}的概率答案在1\sim a_{i+1}中。所以期望为\frac{a_{i+1}}{a_i}\times \frac{1}{a_{i+1}}=\frac{1}{a_i}

• 当a_i<a_{i+1}，由于随机的答案只在1\sim a_i中，而第i+1题正确答案有\frac{a_i}{a_{i+1}}的概率在1\sim a_i中，所以期望为\frac{a_i}{a_{i+1}}\times \frac{1}{a_i}=\frac{1}{a_{i+1}}

综上，答案就是\sum^{n}_{i=1}\frac{1}{max(a_i,a_{i+1})}

#include <cstdio>
#include <iostream>
using namespace std;

const int N=10000010;
int n,a[N];
double ans;

void init()  //题目给出的生成数据的方法
{
    int A,B,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;
}

int main()
{
    init();
    a[n+1]=a[1];  //第1题写第n题的答案
    for (int i=1;i<=n;i++)
        ans+=1/(double)max(a[i],a[i+1]);
    printf("%0.3lf",ans);
    return 0; 
}