自动搬运

查看原文

来自洛谷，原作者为

	Binary_Search_Tree 博客 https://cnblogs.com/bestlxm

搬运于2025-08-24 22:10:17，当前版本为作者最后更新于2019-07-29 14:38:46，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目传送门

因为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}$被(n+1-i)个元素包含，

所以选中$\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;
}