题目
思路来源
官方题解
题解
特殊球不会改变普通球的顺序,所以都是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;
}