题解 P5389 【[Cnoi2019]数学课】

· · 题解

题目传送门

因为a和b的产生方式完全相同，所以a>b与a<b的概率是相等的。

设p表示a=b的概率，那么答案就是\frac{1-p}{2}

问题转化为如何计算a=b的概率。

对于数列中的第i个元素，a_i=\sum_{j=1}^ij=\frac{i(i+1)}{2}

那么恰好选中第i个元素中的一个数的概率:

\frac{3i(i+1)}{n(n+1)(n+2)}×\frac{1}{\frac{i(i+1)}{2}}=\frac{6}{n(n+1)(n+2)}

因为1在数列中被n个元素包含，2----3被(n-1)个元素包含，4----6被(n-2)个元素包含，

所以选中$\frac{i(i-1)}{2}$+1----$\frac{i(i+1)}{2}$中任意一个数的概率为 $\frac{6(n+1-i)}{n(n+1)(n+2)}

所以得到p的表达式

p=\sum_{i=1}^ni×[\frac{6(n+1-i)}{n(n+1)(n+2)}]^2=\frac{36\sum_{i=1}^ni(n+1-i)^2}{[n(n+1)(n+2)]^2}=\frac{3}{n(n+2)}

所以答案是\frac{1-\frac{3}{n(n+2)}}{2}(当n为正无穷时，答案为\frac{1}{2})

推出公式后，代码就非常好写了：

#include <cstdio>
#include <cstring>
#include <cmath>
#include <iostream>
#include <algorithm>
#define M 5000005
#define mod 998244353ll
using namespace std;
long long n;
long long inv(long long x){
    if (x==1) return 1;
    return (mod-mod/x)*inv(mod%x)%mod;
}
int main(){
    scanf("%lld",&n);n%=mod;
    if (!n) printf("%lld",inv(2));
    else printf("%lld",inv(2)*(1-3*inv(n)%mod*inv(n+2)%mod+mod)%mod);
    return 0;
}