单选错位_期望

发布于 2017-12-25  834 次阅读

题目描述

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

 

思路

对于每一个题目，只会被上一个题目影响

设两个相邻的题目(x,y)，不管其他题目如何选，这两个题目选的方案是x*y

而在全部的情况中有min(x,y)种为可以做对的

对于这一题做对的期望为min(x,y)/x*y

让后将每一题的期望加起来就可以了

第一个特殊处理一下即可

 

#include 
#define min(x, y) ((x) < (y) ? (x) : (y))
long long a[10000500];
int main()
{
    freopen("exp.in", "r", stdin);
    freopen("exp.out", "w", stdout);
    int n, 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;
    double ans = 0;
    a[n + 1] = a[1];
    for (int i = 2; i <= n + 1; i++)
        ans += (min(a[i - 1], a[i]) * 1.0) / ((a[i - 1] * a[i]) * 1.0);
    printf("%.3lf\n", ans);
}

 

]]>