luoguP5389 [Cnoi2019]数学课

神仙数学，想复杂了

数学课

最近感觉不在状态（可能是快期末考试了吧），所以随机跳了一题，肉眼可见的数学题

由于 $a, b$ 产生方式相同，所以 $P(a > b) = P(a < b)$ ，因此只需要计算 $P(a = b)$ 即可

考虑 $a = x_k$ 的概率：

设数列为 $\{x_i\}$ ，明显 $x_i = \frac{i (i + 1)}{2}$ ，选出 $x_i, (i \ge k)$ 的概率有 $P(x_i) = \frac{3 i (i + 1)}{n (n + 1)(n + 2)}$ ，再得 $a = x_k$ 的概率有：
$$
\begin{aligned}
P(a = x_k)
& = \sum_{i \ge k} P(x_i) \times \frac{1}{x_i} \\
& = \sum_{i \ge k} \frac{6}{n (n + 1)(n + 2)} \\
& =\frac{6 (n - k + 1)}{n (n + 1)(n + 2)} \\
\end{aligned}
$$
所以：
$$
\begin{aligned}
P(a = b)
& = \sum_{i = 1}^n i \times P(a = x_i)^2 \\
& = \sum_{i = 1}^n i \times (\frac{6 (n - i + 1)}{n (n + 1) (n + 2)})^2 \\
& = \frac{36}{(n (n + 1)(n + 2))^2} \sum_{i = 1}^n i(n - i + 1)^2 \\
& = \frac{3}{n (n + 2)}
\end{aligned}
$$
注意数据范围 $n$ 要开 long long

#include <bits/stdc++.h>
#define LL long long
using namespace std;
const LL P = 998244353;
LL qpow(LL x, LL y)
{
    LL res = 1;
    while (y)
    {
        if (y & 1)
            res = (LL)res * x % P;
        x = (LL)x * x %P;
        y >>= 1;
    }
    return res;
}
int main()
{
    LL n;
    scanf("%lld", &n);
    n %= P;
    if (!n)
        printf("%d", qpow(2, P - 2));
    else
    {
        LL a = ((LL)(n + 2) * n % P - 3 + P) % P;
        LL b = (LL)(n + 2) * n % P * 2 % P;
        printf("%d", (LL)qpow(b , P - 2) * a % P);
    } 
    return 0;
}