the Solution of the Problem P5389

HPXXZYY · 2021-06-06 21:04:41 · 题解

\color{blue}{\texttt{[Problem]}}

你有一个长度为 n 的数列 a_{1 \cdots n}，满足 a_{i} = \sum\limits_{j=1}^{i} j。
你现在需要从数列 a 中选出两个数 v_1,v_2，再任意选择两个正整数 x,y，使得 x \in [1,v_1],y \in [1,v_2]。
其中，v_1,v_2 的值的选取互不影响（即可以相等可以不等），选到 a_{i} 的概率是：
\frac{3 \times i \times (i+1)}{n \times (n+1) \times (n+2)}
而 x,y 也是互相独立的，其选到任意一个符合条件的值的概率是相等的。
问 x>y 的概率是多少，即求 P(x>y) 的值。

\color{blue}{\texttt{[Solution]}}

由于 x,y 的产生方式是相同的，故取值具有对称性，所以 x>y 的概率等于 x<y 的概率，即：

P(x>y)=P(x<y)

所以，答案就是 1 减去 x=y 的概率再除以 2。

依题意得，

a_{i} = \frac{i \times (i+1)}{2}

故而，x 选中 [1,v_1] 某一个数的概率就是：

\frac{1}{\left ( \frac{i\times (i+1)}{2}\right )}

由条件概率公式可知，在 v_1 选中 a_{i} 条件下 x 选中其中任意一个数的概率为：

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

易知，使得 x 有概率取到区间 \left [ \frac{i(i-1)+1}{2}+1,\frac{i(i+1)}{2}\right ] 这 i 个数的 v_1 有 (n+1-i) 个，因此选到这个区间内的任意一个数的概率为：

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

故而选到这个区间的概率为：

i \times \frac{6(n+1-i)}{n(n+1)(n+2)}

所以： $$ \begin{aligned} P(x=y)&=\sum\limits_{i=1}^{n} i \times \left [ \frac{6(n+1-i)}{n(n+1)(n+2)} \right ]^2\\ &=\frac{3}{n(n+2)} \end{aligned} $$ 所以： $$ \begin{aligned} P(x<y)&=\frac{1-P(x=y)}{2}\\ &=\frac{1-\frac{3}{n(n+2)}}{2} \end{aligned} $$ 因为模数是素数，随便拿一个快速幂就可以维护这个式子了。同时，我们可以发现，当 $n \rightarrow \infty$ 时，概率趋近于 $\dfrac{1}{2}$。 $\color{blue}{\texttt{[code]}}

long long n;int ans;
int main(){
    scanf("%lld",&n);n%=mod;
    if (n==0) ans=ksm(2,mod-2);
    else ans=1ll*(mod+1-3ll*ksm(1ll*n*(n+2)%mod,mod-2)%mod)%mod*ksm(2,mod-2)%mod;
    printf("%d",ans);
    return 0;
}