BZOJ2134 单选错位

题解
概率期望

Description

$n$ 道题，第 $i$ 道题有 $a_i$ 个选项。求将正确答案全部右移一位（第 $n$ 题移到第 $1$ 题）之后期望对的题数

Solution

答案 = 期望多少个 $i$ 满足 $ans_i = ans_{i+1}$ 也 = sum $ans_i = ans_{i+1}$ 的期望也就是 $\sum \frac{\min\{a_i, a_{i+1}\}}{a_ia_{i+1}}=\sum\frac{1}{\max\{a_i,a_{i+1}\}}$ （为了方便设 $a_{n+1}=a_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
/**
 * Author: AcFunction
 * Date:   2019-03-20 14:41:06
 * Email:  3486942970@qq.com
**/

#include <bits/stdc++.h>

using namespace std;

int n, A, B, C, a[10000002]; 
double ans; 
int main() {
  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; 
  a[n + 1] = a[1];
  for(int i = 1; i <= n; i++) ans += 1.0 / max(a[i], a[i + 1]); 
  printf("%.3lf\n", ans); 
  return 0; 
}