[ BZOJ 2134 ] 单选错位

\(\\\)

\(Description\)

一共\(N\)道题目，第\(i\)道题有\(A_i\)个选项，现在有一个人做完了所有题目，但将每一道题的答案都写到了下一道题的位置\((\)第\(N\)道写到了第一道的位置\()\)，现在这个人的选项和每道题的正确答案对于每一个选项均为随机，求这个人做对的题目数的期望。

\(N\in [1,10^7]\)

\(\\\)

\(Solution\)

第\(i\)个位置选择了合法的第\(i+1\)个位置的概率，即选了一个范围在\([1,A_{i+1}]\)范围内的数的概率，是\(\frac{min(A_i,A_{i+1})}{A_i}\)。

选对的概率是\(\frac{1}{A_{i+1}}\)，所以第\(i\)个位置做对了第\(i+1\)道题的概率是\(\frac{min(A_i,A_{i+1})}{A_i\times A_{i+1}}=\frac{1}{max(A_i,A_{i+1})}\)。

根据期望的线性性，做对题目总数的期望等于做对每一道题的期望之和，而做对一道题的贡献是\(1\)，所以是做对每一道题的概率之和，求出来每一道的概率之后直接求和就好。

\(\\\)

\(Code\)

#include<cmath>

#include<cstdio>

#include<cctype>

#include<cstdlib>

#include<cstring>

#include<iostream>

#include<algorithm>

#define N 10000010

#define R register

#define gc getchar

using namespace std;

typedef long long ll;

inline int rd(){

  int x=0; bool f=0; char c=gc();

  while(!isdigit(c)){if(c=='-')f=1;c=gc();}

  while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=gc();}

  return f?-x:x;

}

int n,A,B,C,a[N];

int main(){

  n=rd(); A=rd(); B=rd(); C=rd(); a[1]=rd();

  for(R int i=2;i<=n;i++) a[i]=((ll)a[i-1] * A + B) % 100000001;

  for(R int i=1;i<=n;i++) a[i] = a[i]%C+1;

  double ans=1.0/(double)max(a[1],a[n]);

  for(R int i=2;i<=n;++i) ans+=1.0/(double)max(a[i],a[i-1]);

  printf("%.3lf\n",ans);

  return 0;

}

巴特西

[ BZOJ 2134 ] 单选错位

\(Description\)

\(Solution\)

\(Code\)

最新文章

热门文章