【题解】CF1983E
翻译
原题链接
分析
显然，两人得分总和等于所有球的分数之和，所以我们只需要研究一个人即可，这里我们考虑Alice。
分析哪些球会被Alice拿走。我们称前 k k k个球为 1 1 1，其他球为 0 0 0。然后把一个 0 0 0和与前一个 0 0 0之间的所有 1 1 1记为一个组：
01101110011 分为 0 110 1110 0 11
于是第奇数个组的球归Alice所有，考虑上末端（空无所谓），共 n − k + 1 n-k+1 n−k+1个组。
接下来求期望。先考虑 0 0 0。第 i ( i > k ) i(i>k) i(i>k)个球被Alice拿到当且仅当它为第奇数个白球，所以它的贡献为：
⌈ n − k 2 ⌉ n − k ∗ v i \frac{\left \lceil \frac{n-k}{2} \right \rceil }{n-k} * v_{i} n−k⌈2n−k⌉∗vi
0 0 0的总贡献为：
⌈ n − k 2 ⌉ n − k ∑ i = k + 1 n v i \frac{\left \lceil \frac{n-k}{2} \right \rceil }{n-k} \sum_{i=k+1}^{n}v_{i} n−k⌈2n−k⌉∑i=k+1nvi
再考虑 1 1 1的贡献，第 i ( i ≤ k i(i \le k i(i≤k)个球被Alice拿到，当且仅当它属于第奇数个组，每个球放哪个组互相独立，不干扰，同组之间的顺序也不影响贡献。所以 v i v_{i} vi的贡献为：
⌈ n − k + 1 2 ⌉ n − k + 1 ∗ v i \frac{\left \lceil \frac{n-k+1}{2} \right \rceil }{n-k+1} * v_{i} n−k+1⌈2n−k+1⌉∗vi
1 1 1的总贡献为：
⌈ n − k + 1 2 ⌉ n − k + 1 ∑ i = 1 k v i \frac{\left \lceil \frac{n-k+1}{2} \right \rceil }{n-k+1} \sum_{i=1}^{k}v_{i} n−k+1⌈2n−k+1⌉∑i=1kvi
综上，总期望为：
E ( A l i c e ) = ⌈ n − k + 1 2 ⌉ n − k + 1 ∑ i = 1 k v i + ⌈ n − k 2 ⌉ n − k ∑ i = k + 1 n v i E(Alice) = \frac{\left \lceil \frac{n-k+1}{2} \right \rceil }{n-k+1} \sum_{i=1}^{k}v_{i} + \frac{\left \lceil \frac{n-k}{2} \right \rceil }{n-k} \sum_{i=k+1}^{n}v_{i} E(Alice)=n−k+1⌈2n−k+1⌉∑i=1kvi+n−k⌈2n−k⌉∑i=k+1nvi
E ( B o b ) = ∑ i = 1 n − E ( A l i c e ) E(Bob) = \sum_{i=1}^{n} - E(Alice) E(Bob)=∑i=1n−E(Alice)
代码
除法逆元的计算使用 1 x ≡ x ( p − 2 ) ( m o d p ) \frac{1}{x} \equiv x^{(p-2)} \ (mod\ \ p) x1≡x(p−2) (mod p)，其中 p p p为质数，证明在此略。
#include<bits/stdc++.h>
using namespace std;
#define N 500005
#define int long long
const int mod = 1e9+7;
int t, n, k, a[N];
int quick(int x, int t) {int now = 1;while(t) {if(t & 1) now = now * x % mod;x = x * x % mod;t >>= 1;}return now;
}
signed main() {cin>>t;while(t--) {cin>>n>>k;for(int i=1;i<=n;i++) scanf("%lld", a+i);int sum1 = 0, sum2 = 0;for(int i=1;i<=k;i++) sum1 += a[i]; sum1 %= mod;for(int i=k+1;i<=n;i++) sum2 += a[i]; sum2 %= mod;int ans1 = (n-k+1) / 2 * quick(n-k, mod-2) % mod * sum2 % mod;int ans2 = (n-k+2) / 2 * quick(n-k+1, mod-2) % mod * sum1 % mod;int ans = (ans1 + ans2) % mod;printf("%lld %lld\n", ans, ((sum1 + sum2 - ans) % mod + mod) % mod);}return 0;
}