P5389 [Cnoi2019] 数学课

题目描述

聪明的 Cirno 开始学习计算，于是她很开心的算出了从 $1$ 一直加到 $n$。

得到了一个 $n$ 项的数列 : $\{a_n=1+2+3+4+...+n\}$。

为了验证自己算是否算错，她需要以某种规律从数列里取出两个元素 $v_1,v_2$（元素可以相同），并等概率的选出整数 $a\in [1,v_1]$，$b\in [1,v_2]$ 判断哪个比较大。

所以她需要你来计算 $a>b$ 的概率。

某种规律：选到数列第 $i$ 个元素的概率是：

$$\frac{a_i}{\sum _{n=1}^n{a}_n}=\frac{3i\times (i+1)}{n(n+1)(n+2)}$$

输入格式

输入一个正整数 $n$。

输出格式

输出在模 $998244353$ 意义下的概率。

输入输出样例 #1

输入 #1

2

输出 #1

686292993

说明/提示

对于前 $5\mathrm{\%}$ 的数据 $n=3$；

对于前 $15\mathrm{\%}$ 的数据 $n\le 100$；

对于前 $30\mathrm{\%}$ 的数据 $n\le 5000$；

对于前 $55\mathrm{\%}$ 的数据 $n\le {10}^7$；

对于前 $95\mathrm{\%}$ 的数据 $1\le n\le {10}^{18}$；

对于最后 $5\mathrm{\%}$ 的数据 $n=0$ 表示 正无穷；

对于 100% 的数据 $n$ 不为 $998244353$ 的倍数。

题解

显然 $a>b$ 与 $a<b$ 的概率是相等的，那么答案是 $\frac{1-P(a=b)}{2}$。问题转化为如何计算 $P(a=b)$。

数列中的第 $i$ 个元素 $a_i=\sum _{j=1}^{i}j=\frac{i(i+1)}{2}$。那么恰好选中 $a_i$ 的概率为

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

因为 $1$ 在数列中被 $n$ 个元素包含, $2,\dots ,3$ 被 $(n-1)$ 个元素包含, $4,\dots ,6$ 被 $(n-2)$ 个元素包含，$\frac{i(i-1)}{2}+1,\dots ,\frac{i(i+1)}{2}$ 被 $(n+1-i)$ 个元素包含，所以选中 $\frac{i(i-1)}{2}+1,\dots ,\frac{i(i+1)}{2}$ 中任意一个数的概率为 $\frac{6(n+1-i)}{n(n+1)(n+2)}$。因此

$$P(a=b)=\sum _{i=1}^{n}i\times {\left[\frac{6(n+1-i)}{n(n+1)(n+2)}\right]}^2=\frac{36\sum _{i=1}^{n}i(n+1-i{)}^2}{[n(n+1)(n+2){]}^2}=\frac{3}{n(n+2)}$$

所以答案是 $\frac{1}{2}-\frac{3}{2n(n+2)}$（当 $n=+\mathrm{\infty }$ 时, 答案为 $\frac{1}{2}$）。