「SWTR-7」IOI 2077

ID: 5405

远端评测题

1000ms

512MiB

尝试: 0

已通过: 0

难度: 4

上传者:

root

标签>

数学

O2优化

概率论,统计

期望

洛谷月赛

题目背景

友情提醒：本题输入输出量很大，请不要使用 cin 或 scanf。题目最下方附有快读及其使用方法。

赛时提醒：若对于选出的 $m$ 无解，则期望值为 $0$ 。可以结合样例 2 的解释说明以更好理解。

赛时提醒：你需要求的是能力值之和的期望而不是最大值。

小 A 被 FCC 钦定参加 IOI 2077！71 岁老将请求出战！

题目描述

IOI 2077 有 $n$ 位候选参赛者，他们分别编号为 $1\sim n$ 。每位候选参赛者都有一个能力值，且能力值互不相等，第 $i$ 位候选参赛者的能力值为 $a_i$ 。小 A 更喜欢有序的数字，所以他将这 $n$ 位候选参赛者按照能力值从小到大排好了序，即满足 $a_i<a_{i+1}\ (1\leq i<n)$ 。

正式参赛者将会从这 $n$ 位候选参赛者中产生。具体地，所有参赛者将是候选参赛者的一个子串 $[l,r]$ ，即编号为 $l,l+1,\cdots,r$ 的选手将参加 IOI 2077，其中，小 A 的编号为 $k$ 。因为他知道自己被钦定参加 IOI 2077，所以 $l\leq k\leq r$ 。可能的参赛者一共有 $q$ 种情况，每种情况用三个数 $l_i,r_i,k_i\ (l_i\leq k_i\leq r_i)$ 描述，即参赛者为编号在区间 $[l_i,r_i]$ 中的候选参赛者，而小 A 的编号为 $k_i$ 。

由于自己太菜，小 A 对即将到来的 IOI 感到力不从心。他决定选择一些参赛者作为队友，并与他们在赛场上相互帮（zuo）助（bi）。具体地，设正式参赛人数为 $s$ ，那么小 A 会在 $[0,\lfloor\frac{s-1}{2}\rfloor]$ 中等概率随机选择一个数 $m$ ，并从 $s$ 位参赛者中随机选出 $2m$ 个作为他的队友。不过，小 A 不希望自己显得太菜，所以他的能力值 $a_k$ 必须是这 $2m+1$ 个人的能力值的中位数。

俗话说，人多力量大，小 A 希望他与所有选出的队友的能力值之和尽量地大。不过在此之前，他想知道这个值的期望值是多少。请对 $998244353$ 取模，保证答案在该模数下有意义。对于每一种可能的参赛者情况，你都需计算该情况下的答案。为了避免过大的输出，你只需要计算所有答案的异或和。

输入格式

第一行一个整数 $t$ ，表示该测试点 Subtask 编号。
第二行两个整数 $n,q$ ，分别表示候选参赛者个数和情况总数。
第三行 $n$ 个整数 $a_1,a_2,\cdots,a_n$ 表示每个候选参赛者的能力值。保证 $a_i$ 递增。
接下来 $q$ 行，每行三个整数 $l_i,r_i,k_i$ 描述一个可能的参赛者情况。

输出格式

输出一行一个整数，表示所有答案的异或和。

499122189

提示

「样例 1 说明」

第 1 个询问：
因为 $s_1=r_1-l_1+1=5$ ，所以 $m$ 可以为 $0,1$ 或 $2$ 。
$m=0$ 时：小 A 没有队友，那么期望值就是他自身的能力值 $a_{k_1}=a_3=5$ 。
$m=1$ 时：小 A 可以选编号 $(1, 4)$ 或 $(1, 5)$ 或 $(2, 4)$ 或 $(2, 5)$ 的参赛者作为他的队友，能力值之和分别为 $14,15,15,16$ ，期望值为 $\frac{14+15+15+16}{4}=15$ 。
$m=2$ 时：小 A 只能全选，期望值为 $2+3+5+7+8=25$ 。
综上，期望值为 $\frac{5+15+25}{3}=15$ 。
第 2 个询问：
因为 $s_2=r_2-l_2+1=3$ ，所以 $m$ 可以为 $0$ 或 $1$ 。
$m=0$ 时，小 A 没有队友，期望值为 $3$ 。
$m=1$ 时，小 A 无法选择，期望值为 $0$ 。
综上，期望值为 $\frac{3+0}{2}=\frac{3}{2}$ ，对 $998244353$ 取模后为 $499122178$ 。

$15\oplus499122178=499122189$ 。

「数据范围与约定」

本题采用捆绑测试。

记 $s_i=r_i-l_i+1$ 。

Subtask #0（1 point）：是样例。
Subtask #1（10 points）： $s_i\leq 2$ 。
Subtask #2（20 points）： $s_i\leq 16$ ， $q\leq 40$ ， $n\leq 640$ 。
Subtask #3（15 points）： $s_i,q\leq 500$ ， $n\leq 10^5$ 。
Subtask #4（15 points）： $s_i,q\leq 3\times 10^3$ ， $n\leq 10^5$ 。
Subtask #5（15 points）： $s_i,q\leq 2\times 10^5$ ， $n\leq 5\times 10^5$ 。
Subtask #6（24 points）：无特殊限制。

对于 $100\%$ 的数据， $1\leq n,q\leq 2\times 10^6$ ， $1\leq l_i\leq k_i\leq r_i\leq n$ ， $1 \le a_i \le 998244352$ ， $a_i<a_{i+1}\ (1\leq i<n)$ 。

对于所有测试点，时间限制 1s，空间限制 512MB。

「帮助/提示」

关于有理数取余，中位数。

本题输入输出量极大，请注意 I/O 优化。
本题提供有符号 32 位整数快读模板，保证读入用时不超过 250ms：

#define gc getchar()
inline int read(){
	int x=0; bool sgn=0; char s=gc;
	while(!isdigit(s))sgn|=s=='-',s=gc;
	while(isdigit(s))x=(x<<1)+(x<<3)+(s-'0'),s=gc;
	return sgn?-x:x;
}

// 如果需要读入直接调用 read() 即可。
// 一个例子（与正解无关，仅供参考）：

int t=read(),n=read(),q=read();
int a[2000005],l[2000005],r[2000005],k[2000005];
for(int i=1;i<=n;i++)a[i]=read();
for(int i=1;i<=q;i++)l[i]=read(),r[i]=read(),k[i]=read();

// 这样你就可以在 250ms 内读入全部数据了。

「题目来源」

Sweet Round 07 C。
idea & solution：SSerWarriors_Cat；data：Alex_Wei ；验题：chenxia25。

IOI 2077 落下帷幕，小 A 凭借出（dui）色（you）的发（bang）挥（zhu）成功 AK 了 IOI，这不禁让他回想起曾经满腔热血的自己，以及和他共同奋斗在 OI 路上的战友们。如今他们虽已天各一方，说起来也有十几年没见过面了，但他们真挚的友谊未曾淡去，也将永远不会褪色。

“爷爷，您手机里有段录音，还写着 'ycx txdy!'。”
“哦，是嘛？放出来听听。”

“I AK IOI. I AK ACM World Final. I AK Universe OI. I think all of you are vegetable chickens.”
“I AK IOI. I AK ACM World Final. I AK Universe OI. I think all of you are vegetable chickens.”
“I AK IOI. I AK ACM World Final. I AK Universe OI. I think all of you ............”

2077.7.7

#P7875. 「SWTR-7」IOI 2077