题解 P7875 【IOI 2077】
dingcx
·
·
题解
这是一道数学题。
思路
参赛者满足 能力值 \le 小 A 的人数 等于 能力值 \ge 小 A 的人数，即在 l ~ k-1 中选的人数 等于 在 k+1 ~ r 中选的人数。
枚举这个相等的人数，计算此时的期望：
$1$ 人：通过计算每个人被选中的概率乘以每个人的能力值得到答案。在 $l$ ~ $k-1$ 中每个人被选中的概率是 $\frac{1}{k-l}$，在 $k+1$ ~ $r$ 中每个人被选中的概率是 $\frac{1}{r-k}$。于是能力期望值为 $\frac{a_l+...+a_{k-1}}{k-l}+\frac{a_{k+1}+...+a_r}{r-k}+a_k$，可用前缀和优化（$s$ 为前缀和数组）：
$$\frac{s_{k-1}-s_{l-1}}{k-l}+\frac{s_r-s_k}{r-k}+a_k$$
$2$ 人：在 $l$ ~ $k-1$ 中每个人被选中的概率是 $\frac{2}{k-l}$，在 $k+1$ ~ $r$ 中每个人被选中的概率是 $\frac{2}{r-k}$。于是能力期望值为
$$2\times\frac{s_{k-1}-s_{l-1}}{k-l}+2\times\frac{s_r-s_k}{r-k}+a_k$$
$\cdots\cdots
$$mi\times\frac{s_{k-1}-s_{l-1}}{k-l}+mi\times\frac{s_r-s_k}{r-k}+a_k$$
$mi+1$ 人：能力期望值为 $0$。
$\cdots\cdots
于是，总的能力期望值：
$$\frac{(mi+1)\times a_k+(1+...+mi)\times \frac{s_{k-1}-s_{l-1}}{k-l}+(1+...+mi)\times\frac{s_r-s_k}{r-k}}{\lfloor \frac{r-l}{2} \rfloor}$$
也就是
$$\frac{(mi+1)\times a_k+\frac{\normalsize mi*(mi+1)}{\normalsize 2}\times (\frac{\normalsize s_{k-1}-\normalsize s_{l-1}}{\normalsize k-l}+\frac{\normalsize s_r-s_k}{\normalsize r-k})}{\lfloor \frac{\normalsize r-l}{\normalsize 2} \rfloor}$$
接下来考虑怎么有理数取余，也就是 [这道题](https://www.luogu.com.cn/problem/P2613)。
注意**不能**先上下通分，把答案的分子分母算出来，然后取余。这样不仅要考虑各种细节，还会超时。（~~我就是因为这样做而没有在赛时做出这道题~~）
正确的做法是先**预处理** $2\times10^6$ 内每个数关于 $998244353$ 的**逆元**，存到一个数组上（记作 $inv$），这样就把除转换成乘了。
还有一个**细节**，就是如果预处理前缀和数组的时候取模了，那前缀和的差可能会 $<0$。因此要么预处理时不取模，要么在计算答案时 $+mod$。
## 代码
```cpp
#include<cstdio>
#include<algorithm>
#define ll long long
using namespace std;
const int MAXN=2e6+10,MOD=998244353;
ll a[MAXN],s[MAXN],inv[MAXN];
int read(){
int num=0,sign=1; char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')sign=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){num=(num<<1)+(num<<3)+ch-'0';ch=getchar();}
return num*sign;
}
int main(){
int type=read(),n=read(),m=read(),ans=0;
for(int i=1;i<=n;i++)
a[i]=read(),s[i]=(s[i-1]+a[i])%MOD; //算前缀和
inv[1]=1; //预处理逆元数组
for(int i=2;i<=2e6;i++)
inv[i]=(MOD-(MOD/i*inv[MOD%i]%MOD))%MOD;
while(m--){
ll l=read(),r=read(),k=read();
ll mi=min(k-l,r-k),res;
res=((mi+1)*a[k]%MOD+((mi*(mi+1)/2)%MOD)*(((s[k-1]-s[l-1]+MOD)*inv[k-l]%MOD+(s[r]-s[k]+MOD)*inv[r-k]%MOD)%MOD)%MOD)%MOD;
ans^=(res*inv[(r-l)/2+1]%MOD);
//套公式
}
printf("%d\n",ans);
return 0; //华丽结束
}
```
求点赞~