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)，
可以把特别球的总分集在一个特别球上，平常球同理
也可以看成是摊成均匀分摊在这多少个球上
代码

2. #include<bits/stdc++.h>
3. using namespace std;
4. #define rep(i,a,b) for(int i=(a);i<=(b);++i)
5. #define per(i,a,b) for(int i=(a);i>=(b);--i)
6. typedef long long ll;
7. typedef double db;
8. typedef pair<int,int> P;
9. #define fi first
10. #define se second
11. #define pb push_back   
12. #define dbg(x) cerr<<(#x)<<":"<<x<<" ";
13. #define dbg2(x) cerr<<(#x)<<":"<<x<<endl;
14. #define SZ(a) (int)(a.size())
15. #define sci(a) scanf("%d",&(a))
16. #define pt(a) printf("%d",a);
17. #define pte(a) printf("%d\n",a)
18. #define ptlle(a) printf("%lld\n",a)
19. #define debug(...) fprintf(stderr, __VA_ARGS__)
20. using namespace std;
21. const int N=4e5+10,mod=1e9+7;
22. int t,n,k,inv[N],s1,s2,sum,v,alice,bob;
23. int halfmore(int x){
24.     return (x+1)/2;
25. }
26. int main(){
27.     inv[0]=inv[1]=1;
28.     rep(i,2,N-1)inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;
29.     sci(t);
30.     while(t--){
31.         sum=s1=s2=0;
32.         sci(n);sci(k);
33.         rep(i,1,n){
34.             sci(v);
35.             sum=(sum+v)%mod;
36.             if(i<=k)s1=(s1+v)%mod;
37.             else s2=(s2+v)%mod;
38.         }
39.         s1=1ll*s1*inv[k]%mod;
40.         s2=1ll*s2*inv[n-k]%mod;
41.         int blank=n-k+1,ball=n-k;
42.         alice=(1ll*halfmore(blank)*k%mod*inv[blank]%mod*s1%mod+1ll*halfmore(ball)*s2%mod)%mod;
43.         bob=(sum+mod-alice)%mod;
44.         printf("%d %d\n",alice,bob);
45.     }
46.     return 0;
47. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！qidao123.com:ToB企服之家，中国第一个企服评测及软件市场,开放入驻,技术点评得现金