【解题报告】 洛谷P1297 单选错位

题目链接

https://www.luogu.com.cn/problem/P1297

思路

这道题目一看是一道期望的题目，但是这个不用 DP ，我们发现，后一个和前一个答案的情况总共有 ai−1×aia_{i-1} \times a_i 种

然后我们为了使得这两种答案重合的概率肯定是 min{ai−1,ai}ai−1×ai\dfrac {min \{ a_{i-1},a_i\}} {a_{i-1} \times a_i}

上下约分 1max{ai−1,ai}\dfrac 1 {max \{a_{i-1},a_i \}}

于是我们直接统计一下答案就可以了

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
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
using namespace std;
const int maxn=10000005;
double ans;
int a[maxn];
int n,A,B,C;
void init()
{
	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;
}
int main()
{
	init();
	a[0]=a[n];
	for(int i=1;i<=n;i++)
		ans+=(double)(1.0/max(a[i-1],a[i]));
	printf("%.3lf\n",ans);
	return 0;
}