CF1983E I Love Balls

发表于 更新于 阅读次数： 本文字数： 719 阅读时长 ≈ 3 分钟

Problem - E - Codeforces

爱丽丝和鲍勃玩摸球游戏。有 \(n\) 个球，其中 \(k\) 个是特殊球。每个球都有其价值。

他们轮流且不放回地摸球，每回合随机摸一个球并获得该球的价值。特别地，如果摸到了特殊球（且至少还有一个球）则这名玩家继续摸球。如果摸到的是普通球，则换人摸球。这样轮流摸球直到没有剩余球，游戏结束。Alice先手。

求游戏结束时双方的期望得分，对取模 \(10^9+7\) 。

\(t\le2\times10^5,1\le k\le n\le 4\times 10^5,1 \le v_i \le 10^7,\sum n\le 5\times 10^5\)

Solution

看别人题解的时候看见一个很常见的结论，先记录一下

取球的过程可以看作是n个球提前排列好，然后依次去取。

所以取到每个普通球的概率都是相同的（特殊球同理）。

我们尝试模拟一下两个人做摸球游戏，发现如果摸到了特殊球就会一直摸下去，直到遇到了普通球或者摸完了为止。摸到了普通球就换人，摸完了则游戏结束。

先考虑普通球的贡献。由于某个玩家摸到了特殊球就会继续摸，直到他摸到了普通球（或者没球了）换人。所以这 \(n-k\) 个普通球一定是交替分配给两人的。Alice将会得到奇数位上的所有普通球，对于某个普通球而言被分配到奇数位上的概率为 \(\frac{\lceil\frac{n-k}{2}\rceil}{n-k}\)；Bob将会得到偶数位上的所有普通球，对应概率为 \(\frac{\lfloor\frac{n-k}{2}\rfloor}{n-k}\)​。

接着考虑特殊球。\(n-k\) 个普通球产生了\(n-k+1\) 个回合区间，每个特殊球都会等概率的出现在这 \(n-k+1\) 个区间中。其中奇数回合内的所有球由Alice得到，概率为 \(\frac{\lceil\frac{n-k+1}{2}\rceil}{n-k+1}\)；偶数回合内的所有球由Bob得到，概率为 \(\frac{\lfloor\frac{n-k+1}{2}\rfloor}{n-k+1}\)。

最终期望为每个球的价值乘以摸到的概率。

Code

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
43
44
45
46
47
48
49
50
51
52
53
#define N 1000010
#define p 1000000007ll

LL n,k;
LL a[N];

LL qpow(LL a,LL b)
{
    LL ans=1;
    while(b)
    {
        if(b&1) ans=ans*a%p;
        a=a*a%p;
        b>>=1;
    }
    return ans%p;
}

LL inv(LL x)
{
    return qpow(x,p-2);
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cout.precision(10);
    int t=1;
    cin>>t;
    while(t--)
    {
        cin>>n>>k;
        for(int i=1;i<=n;i++)
        {
            cin>>a[i];
        }
        LL ans1=0,ans2=0,inv1=inv(n-k),inv2=inv(n-k+1);
        for(int i=k+1;i<=n;i++)
        {
            ans1=(ans1+(n-k+1)/2*a[i]%p*inv1)%p;
            ans2=(ans2+(n-k)/2*a[i]%p*inv1)%p;
        }
        for(int i=1;i<=k;i++)
        {
            ans1=(ans1+(n-k+2)/2*a[i]%p*inv2)%p;
            ans2=(ans2+(n-k+1)/2*a[i]%p*inv2)%p;
        }
        cout<<ans1<<" "<<ans2<<endl;
    }
    return 0;
}