【每日一题】洛谷 P1297（数学期望）
想她一次就背十个单词，当我英语过六级后，我就去告诉她，我很在意她
一天一道数论题，当我可以秒杀数论题的时候，就开始做 DP
今日份快乐：洛谷 P1297 传送门
明天份快乐：洛谷 P1621 传送门
有 n 个题，每个题有 ai 个选项，给出一份正确答案，把每个题的正确答案填到后一道上，最后一个题填到第一个题上。问：做对的题目个数的期望值，保留三位小数
分析很明显，每道题都可以作为一个独立事件，并且都为古典概率事件，则 E(x) = ∑1n\sum_1^n∑1n Pi 。也就是把所有事件的概率加起来。
对于任何一个题 x，前一个题的选择有 a[x-1] 个，这个题的选择有 a[x] 个，则：
两个题答案的组合数为：a[x-1] * a[x]
两个题答案相同的情况为：min(a[x], a[x - 1])
则： Px = min(a[x],a[x−1])a[x−1]∗a[x]{min(a[x], a[x - 1])\over a[x-1] * a[x]}a[x−1]∗a[x]min(a[x],a[x−1])
我们可以继续对上式进行化简，当
a[x] >= a[x-1] 时：Px = a[x−1]a[x−1]∗a[x]{ a[x - 1]\over a[x-1] * a[x]}a[x−1]∗a[x]a[x−1] = 1a[x]{ 1 \over a[x]}a[x]1 = 1max(a[x],a[x−1]){ 1 \over max(a[x], a[x - 1])}max(a[x],a[x−1])1 a[x] < a[x-1] 时：Px = a[x]a[x−1]∗a[x]{ a[x ]\over a[x-1] * a[x]}a[x−1]∗a[x]a[x] = 1a[x−1]{ 1 \over a[x-1]}a[x−1]1 = 1max(a[x],a[x−1]){ 1 \over max(a[x], a[x - 1])}max(a[x],a[x−1])1结合上述两种情况，得：Px = 1max(a[x],a[x−1]){ 1 \over max(a[x], a[x - 1])}max(a[x],a[x−1])1
用 O( n ) 得时间复杂度去算出 Px 并求和
#include
using namespace std;
const int maxn = 1e7 + 5;
int a[maxn];
int main(){
ios::sync_with_stdio(false);
int n, A, B, C;
cin >> 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;
double res = 0; a[0] = a[n];
for (int i = 1; i <= n; i++) res += 1.0 / max(a[i], a[i-1]);
printf("%0.3lf\n", res);
return 0;
}
坚持的时候很狼狈，等成功以后，丑的还是丑的
