Codeforces Round #956 (Div. 2) and ByteRace 2024 E. I Love Balls（概率期望）

题目

思路来源

官方题解

题解

特殊球不会改变普通球的顺序，所以都是alice拿一半里较多的部分

n-k+1一半向上取整就是(n-k+2)/2，同理n-k个一般向上取整(n-k+1)/2

每个特殊球独立地来看，在每个空隙的概率相同

所以分别统计特殊球和非特殊球的分数

另外一个做法是，根据E(x+y)=E(x)+E(y)，

可以把特殊球的总分集在一个特殊球上，普通球同理

也可以看成是摊成平均分摊在这若干个球上

代码

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
typedef long long ll;
typedef double db;
typedef pair<int,int> P;
#define fi first
#define se second
#define pb push_back    
#define dbg(x) cerr<<(#x)<<":"<<x<<" ";
#define dbg2(x) cerr<<(#x)<<":"<<x<<endl;
#define SZ(a) (int)(a.size())
#define sci(a) scanf("%d",&(a))
#define pt(a) printf("%d",a);
#define pte(a) printf("%d\n",a)
#define ptlle(a) printf("%lld\n",a)
#define debug(...) fprintf(stderr, __VA_ARGS__)
using namespace std;
const int N=4e5+10,mod=1e9+7;
int t,n,k,inv[N],s1,s2,sum,v,alice,bob;
int halfmore(int x){
    return (x+1)/2;
}
int main(){
    inv[0]=inv[1]=1;
    rep(i,2,N-1)inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;
    sci(t);
    while(t--){
        sum=s1=s2=0;
        sci(n);sci(k);
        rep(i,1,n){
            sci(v);
            sum=(sum+v)%mod;
            if(i<=k)s1=(s1+v)%mod;
            else s2=(s2+v)%mod;
        }
        s1=1ll*s1*inv[k]%mod;
        s2=1ll*s2*inv[n-k]%mod;
        int blank=n-k+1,ball=n-k;
        alice=(1ll*halfmore(blank)*k%mod*inv[blank]%mod*s1%mod+1ll*halfmore(ball)*s2%mod)%mod;
        bob=(sum+mod-alice)%mod;
        printf("%d %d\n",alice,bob);
    }
    return 0;
}