题目描述
聪明的 Cirno 开始学习计算，于是她很开心的算出了从 $1$ 一直加到 $n$。
得到了一个 $n$ 项的数列 : $\set{ 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\limits_{n=1}^n a_n}=\frac{3i\times(i+1)}{n(n+1)(n+2)} $$
输入格式
输入一个正整数 $n$。
输出格式
输出在模 $998244353$ 意义下的概率。
输入输出样例 #1
输入 #1
1 | |
输出 #1
1 | |
说明/提示
对于前 $5%$ 的数据 $n = 3$；
对于前 $15%$ 的数据 $n \le 100$；
对于前 $30%$ 的数据 $n \le 5000$；
对于前 $55%$ 的数据 $n \le 10^7$；
对于前 $95%$ 的数据 $1\le n \le 10^{18}$；
对于最后 $5%$ 的数据 $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 = + \infty$ 时, 答案为 $\frac{1}{2}$）。
