题解：CF1983E I Love Balls

Ether13 · 2024-07-08 10:44:49 · 题解

题意：有 n 个球，其中 k 个是特殊球。每个球都有一个权值。

在每个回合中，当前的玩家随机挑选一个球，并将该球的价值加到自己的分数中，游戏开始时的分数为 0 ，被选中的球将从游戏中移除。如果选中的球是特殊球，且至少还有一个球，则由同一名玩家进行下一轮游戏。如果选中的球不是特殊球，则由下一位玩家进行下一轮游戏。没有球时游戏结束。

Alice 先手，求游戏结束时双方的期望得分，对 10^9+7 取模。

做法：

先不考虑两名玩家，若只有一个玩家拿球，显然拿出的球是一个排列。

考虑每次换人都是非特殊球，则根据非特殊球将排列划分为 n-k+1 段，其中前 n-k 段每段最后都是一个非特殊球。那么这些非特殊球也是一个排列。注意到 n-k 段中偶数位对 Bob 有贡献，奇数位对 Alice 有贡献。那么对于一个非特殊球，其对 Alice 有贡献的概率是 \frac{\lceil\frac{n-k}{2}\rceil}{n-k} ，对 Bob 有贡献的概率是 \frac{\lfloor\frac{n-k}{2}\rfloor}{n-k}

对于特殊球，其有 n-k+1 个位置可以放，则仍然是偶数位对 Bob 有贡献，奇数位对 Alice 有贡献。对 Alice 造成贡献的概率是 \frac{\lceil\frac{n-k+1}{2}\rceil}{n-k+1}，对 Bob 造成贡献的概率是 \frac{\lfloor\frac{n-k+1}{2}\rfloor}{n-k+1}。

那么期望直接用权值乘概率算即可。

核心代码如下：

ll ea=0,eb=0,invn=qpow(n-k,MOD-2),invn1=qpow(n-k+1,MOD-2);
rep(i,k+1,n){
    ea=(ea+v[i]*((n-k+1)/2)%MOD*invn%MOD)%MOD;
    eb=(eb+v[i]*((n-k)/2)%MOD*invn%MOD)%MOD;
}
n=n-k;
rep(i,1,k){
    ea=(ea+v[i]*(n/2+1)%MOD*invn1%MOD)%MOD;
    eb=(eb+v[i]*((n+1)/2)%MOD*invn1%MOD)%MOD;
}
printf("%lld %lld\n",ea,eb);