Burnling's Blog
0%

CF1983E I Love Balls

发表于 更新于 分类于 ，

题意简述

Alice 和 Bob 正在玩一个游戏。有 $n$ 个球，其中 $k$ 个是特殊球。每个球都有一个与之关联的值。

玩家轮流进行游戏。在每一轮中，玩家随机选一个球并将该球的值加到他们的得分中，初始得分为 $0$。被选中的球会从游戏中移除。如果选中的球是特殊球，且至少还有一个球剩余，则同一个玩家继续下一轮。如果选中的球不是特殊球，则下一个玩家进行他们的回合。

他们一直玩这个游戏直到没有球剩余。Alice 先开始。

求游戏结束时两个玩家的期望得分模 $10^9+7$。

“The first k balls are special” 没看见这句 导致我盯着一篇篇题解想了好久凭什么他们都钦定前 $k$ 个球为特殊球……

思路分析

因为双方都是在 $N$ 个球里面随机选球，所以可以看作将 $N$ 个球打乱顺序后让二人按顺序选。

由于拿到特殊球后可以再选一个，所以选到特殊球对当前玩家拿到普通球的位置及顺序都是相同的。

换言之，如果不去关注特殊球都被谁拿走了，我们可以发现普通球是被轮流拿走的。

又由于 Alice 先手，所以 Alice 在所有普通球中拿走了所有奇数位上的球；Bob 拿走了所有偶数位上的球。

所以每个普通球有 $\dfrac{\lceil \dfrac{N-K}{2}\rceil}{N-K}$ 的概率被 Alice 拿到，有 $\dfrac{\lfloor \dfrac{N-K}{2}\rfloor}{N-K}$ 的概率被 Bob 拿到。

再去考虑特殊球。

在一开始， $N-K$ 个普通球中，共有 $N-K+1$ 个空隙可以插入特殊球。

易知，这 $N-K+1$ 个空隙的奇数空隙上的特殊球被 Alice 拿走，偶数位空隙上的特殊球被 Bob 拿走。

又由于特殊球并不改变普通球空隙的个数，所以在空隙中可以插入任意个特殊球。

所以每个特殊球有 $\dfrac{\lceil \dfrac{N-K+1}{2}\rceil}{N-K+1}$ 的概率被 Alice 取到，有 $\dfrac{\lfloor \dfrac{N-K+1}{2}\rfloor}{N-K+1}$ 的概率被 Bob 取到。

如果设 $t_1$ 表示普通球平均权值，$t_2$ 表示特殊球平均权值，

那么 Alice 期望得分即为 $\dfrac{\lceil \dfrac{N-K}{2}\rceil}{N-K} \times t_1 + \dfrac{\lceil \dfrac{N-K+1}{2}\rceil}{N-K+1} \times t_2 $。

同理知 Bob 的期望得分即为 $\dfrac{\lfloor \dfrac{N-K}{2}\rfloor}{N-K} \times t_1 + \dfrac{\lfloor \dfrac{N-K+1}{2}\rfloor}{N-K+1} \times t_2 $。

由于模数为质数，所以直接费马小定理求逆元即可。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include<bits/stdc++.h>
using namespace std;

const int maxN = 5e5 + 10;
const int MOD = 1e9+7;

int A[maxN];

long long QuickPow(long long a,long long b){
    long long ans = 1;
    while(b){
        if(b & 1) ans = ans * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return ans;
}

inline void solve(){
    int N,K;
    scanf("%d%d",&N,&K);
    long long sum = 0;
    long long t = 0;
    long long c = 0;
    for(int i = 1;i<=N;i++){
        scanf("%d",&A[i]);
        sum += A[i];
        (i <= K ? c : t) += A[i];
    }
    long long t1 = ((N-K+1) >> 1) * t % MOD * QuickPow(N-K,MOD-2) % MOD;
    long long t2 = ((N-K) >> 1) * t % MOD * QuickPow(N-K,MOD-2) % MOD;
    long long t3 = ((N-K+2) >> 1) * c % MOD * QuickPow(N-K+1,MOD-2) % MOD;
    long long t4 = ((N-K+1) >> 1) * c % MOD * QuickPow(N-K+1,MOD-2) % MOD;
    printf("%lld %lld\n",(t1+t3)%MOD,(t2+t4)%MOD);
}

int main(){
    int T;
    scanf("%d",&T);
    while(T--) solve();
    return 0;
}