摘要:数理基础题

luogu1297_[国家集训队]单选错位

题面

tutorial

考虑什么情况下把$i-1$的答案写到$i$上才会正确,就只有两空答案相等这一种情况.

两空的答案总情况数是$a_{i-1} \times a_i$,选到两个相等的答案的情况有$\min\{ a_{i-1} , a_i \}$种,那么每个位置发生相等的概率为$\frac{\min\{ a_{i-1} , a_i \}}{a_{i-1} \times a_i}$,乘上取值$1$即得这个位置上选对的期望,根据线性性相加即可.

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include "cstdio"
#include "iostream"
#include "cstring"
#include "cctype"
#include "iomanip"
#include "algorithm"
#define R register
#define debug(x) printf("debug:%d\n",x)
#define INF 0x3f3f3f3f
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
typedef long long lxl;
char buf[1<<21],*p1=buf,*p2=buf;
const int big=10000010;
double ans;
lxl n,A,B,C;
lxl a[big];
inline lxl read()
{
    char c(getchar());
    lxl x(0);
    for(;!isdigit(c);c=getchar());
    for(;isdigit(c);x=(x*10)+(c^48),c=getchar());
    return x;
}
inline void init()
{
    #ifndef ONLINE_JUDGE
        freopen("data.in","r",stdin);
    #endif
    scanf("%lld%lld%lld%lld%lld", &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(void)
{
    init();
    for(R int i(2);i<=n;++i)ans+=(double)std::min(a[i],a[i-1])/(double)(a[i-1]*a[i]);
    ans+=(double)std::min(a[1],a[n])/(double)(a[1]*a[n]);
    std::cout<<std::fixed<<std::setprecision(3)<<ans;putchar('\n');
    return 0;
}