ABC360E Sol || 人类智慧 1.0

CarroT1212 · 2024-07-01 10:45:28 · 题解

提供一种应该不太一样且码量骤减的人类智慧做法，目前卡长后是 AT 最短解。

设每次选到的两个数为 a,b，黑球目前在 x。

• 如果 a\neq x 且 b\neq x，那么这轮操作就跟 x 没有关系，x 原地不动，概率为 \frac{(n-1)^2}{n^2}。
• 如果 a=b=x，那么 x 同样保持不动，概率为 \frac{1}{n^2}。
• 如果 a=x 或 b=x，那么 x 等概率地换到除它以外的任何一个位置，每一位概率都为 \frac{2}{n^2}。

这时我们动用人类智慧：注意到前两种操作结果相同，于是你从第一种操作里随便拿一种情况分给第二种，使第二种操作的概率变成 \frac{2}{n^2}，这样后面两种操作就可以合并起来了。变成，每次操作：

也就是说，只要 x 在这个定义下“受到影响”过一次，那么它的位置就会完全随机，不管受到几次影响都一样。这样 x 的期望值就为 \frac{n+1}{2}。否则一次都没受影响就是 x=1。

即答案为 (\frac{(n-1)^2-1}{n^2})^k+[1-(\frac{(n-1)^2-1}{n^2})^k]\cdot\frac{n+1}{2}。

ll qp(ll x,ll y=P-2) { return y?(y&1?x:1)*qp(x*x%P,y>>1)%P:1; }
ll n,k,p;
void mian() {
    scanf("%lld%lld",&n,&k);
    p=qp(((n-1)*(n-1)+P-1)%P*qp(n*n%P)%P,k);
    cout<<(p+(1+P-p)*((n+1)*qp(2)%P))%P;
}

感觉自己赛时能想到真是太厉害了。