摘要:数理基础题
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; }
|