題目

思路來源

官方題解

題解

特殊球不會改變普通球的順序，所以都是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;
}