P1297 [国家集训队] 单选错位
2026-05-10
题目大意
给定 n 道题目,每个题目有 ai 个选项,每个选项被选择的概率相同,但是上一个题的选项会被填写到下一个题,问期望正确的题的个数。
数据范围: 1≤n≤107,1≤ai≤108。
题解
设随机变量 Xi∈{0,1} 代表第 i 道题是否正确,则显然正确题目总数 X=∑i=1nXi,利用期望线性性,则有 E(X)=∑i=1nE(Xi),容易发现,对于每道题做对的期望实际就是做对这道题的概率。
于是,第 i 题正确答案在 ai 中取,而填的答案在 ai−1 中取,则有:
P(Xi=1)=ai1×ai−11×min(ai,ai−1)=max(ai,ai−1)1
代码
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
typedef long long LL;
typedef long double LD;
const int N = 1e7+10;
int n;
LL a[N];
int main() {
int A , B , C;
scanf("%d%d%d%d%lld" , &n , &A , &B , &C , &a[1]);
for(int i = 2 ; i <= n ; i ++)
a[i] = (a[i-1]*A+B)%100000001ll;
for(int i = 1 ; i <= n ; i ++)
a[i] = a[i] % C + 1;
LD res = 1.0l / max(a[1] , a[n]);
for(int i = 2 ; i <= n ; i ++) {
res += 1.0l / max(a[i] , a[i-1]);
}
printf("%.3Lf\n" , res);
return 0;
}