自动搬运

查看原文

来自洛谷，原作者为

	dingcx 不如回头再看一眼题面

搬运于2025-08-24 22:33:52，当前版本为作者最后更新于2021-09-25 23:29:42，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

这是一道数学题。

思路

参赛者满足 能力值 $\le$ 小 A 的人数 等于 能力值 $\ge$ 小 A 的人数，即在 $l$ ~ $k-1$ 中选的人数 等于 在 $k+1$ ~ $r$ 中选的人数。

枚举这个相等的人数，计算此时的期望：

$0$ 人：期望值为 $a_k$（就这一种）

$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$

$\min(k-l,r-k)$（记作 $mi$）人，能力期望值为

$$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$

$\lfloor \frac{r-l}{2} \rfloor$ 人：能力期望值为 $0$。

于是，总的能力期望值：

$$\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} $$

接下来考虑怎么有理数取余，也就是 这道题。

注意不能先上下通分，把答案的分子分母算出来，然后取余。这样不仅要考虑各种细节，还会超时。（我就是因为这样做而没有在赛时做出这道题）

正确的做法是先预处理 $2\times10^6$ 内每个数关于 $998244353$ 的逆元，存到一个数组上（记作 $inv$），这样就把除转换成乘了。

还有一个细节，就是如果预处理前缀和数组的时候取模了，那前缀和的差可能会 $<0$。因此要么预处理时不取模，要么在计算答案时 $+mod$。

代码

#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; //华丽结束
}

求点赞~