单选错位_期望

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


题目描述

 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);
}

 

]]>


「墨泼三千烟火,许你一世迷离」