luogu#P11897. 「LAOI-9」多维空间中的游戏
「LAOI-9」多维空间中的游戏
题目背景
我爱你,所以想和你玩游戏。
而不是我想和你玩游戏,所以爱你。
她静静地凝视着你,目光却与往常截然不同——她的脸颊泛起一片绯红,呼吸也变得急促。
你明白,这注定是一场无法善终的相遇,神明已经悄然否定了你们的未来。
虽然你从未见过神明,但你确信无疑,神明已然做出了选择:将她召回那遥远的多维世界。
她是来自更高维度的存在,因为某种未知的原因降维至此。在那个街头,所有人都以一种奇怪的眼神看着你的时候,你收留下了流浪街头、饥肠辘辘的她。
她,只不过是以一种恰好符合你审美与期待的模样出现。
而你,只不过是一个平凡无奇的普通人,相貌平平、能力平平,在浩瀚宇宙中微不足道。
你不明白,为何她会对你心生好感?
你不明白,为何她愿意与你一同游戏?
你不明白,为何你,也会对这场分离,感到悲痛流涕?
你对她绝对没有感情的!
你对她没有感情的。
你对她没有感情?
然而,神明的意志终究不可违逆。她将被驱散回多维世界。就在离别前夕,她开口说道:
「我想再和你玩一次……多维空间中的游戏……」
就算你赢了,也改变不了什么。
题目描述
小 和小 正在玩一个有趣的游戏。
游戏将在一个 $\underbrace{2\times2\times2\times\cdots\times2}_{k 个 2}$ 的 维空间中进行。最小的节点的坐标为 ,最大的节点的坐标为 。
下面是 时的情况:
小 和小 各执一枚 维空间中的点。
小 和小 轮流操作,小 先手。
定义一个维度为可操作的,当且仅当两个点中存在至少一个点在这个维度上的坐标不为 。然后,操作方可以将两个点的某个可操作的维度的坐标置为 。
如图,这是一个合法的操作:
这也是一个合法的操作:
但是这不是一个合法的操作,因为两个点在这个维度上的坐标均为 :
无法操作者输。
相信大家一定发现了,我们可以将任意一个坐标编码为一个二进制数。例如对于坐标 ,可以编码为 ,对应十进制数 。
小 和 将进行 轮游戏。两人绝顶聪明,都想要自己赢。每一轮双方点的位置将会随机生成,进一步地,生成到编码为 的坐标的概率为 。
由于小 先手,所以每轮她们将会划定一个可落子区域 ,其他区域则为不可落子区域。如果小 初始的点坐标编码后的值在区间 外,则将会判为小 胜。(此规则对小 不生效,也就是即使小 初始的点坐标编码后的值在区间 外,也不会直接判为小 胜)
现在对于第 轮,可落子区域为 ,小 会有 个询问,每个询问为当她的点被随机到编号为 的坐标,且小 的点按照 的概率随机生成时,她的胜率为多少。答案对 取模。
输入格式
第一行一个正整数 表示子任务编号,特殊地,样例的编号为 。
接下来一行一个正整数 表示数据读入输出方法。当 时,你需要在下一行接着读入一个整数 表示随机种子。
接下来一行一个正整数 表示维度数。
接下来一行 个非负整数 表示生成到编码为 的坐标的概率为 。
接下来一行一个正整数 表示游戏轮数。
接下来 组询问,对于第 组询问(下标从 开始):
每组询问第一行三个整数,表示 。
当 时,接下来一行 个整数 ,表示每次小 的询问。
当 时,接下来小 的第 个询问(下标从 开始) 为 。
对于 C++ 选手,我们下发了一份数据读入模板 down.cpp
,您只需要完善其中的代码部分即可。
输出格式
当 时,对于第 组询问输出一行 个整数,表示这组询问所有答案模 后的值。
当 时,对于每组询问输出一行一个整数,表示这组询问所有答案模 后的异或和。
0
0
2
0 1 998244351 2
2
1 2 3
2
2 0 1
2 3
3
1 1
0
1
50007
3
1 2 3 4 5 6 7 998244326
1
2 0 7
0
提示
样例 1 解释
对于第一组询问,当小 的点在编号为 的坐标时,由于超出了可落子区域,小 胜;当小 的点在编号为 的坐标时,小 胜;当小 的点在编号为 的坐标时,小 胜。
故在模意义下,小 的胜率:。
样例 2 解释
解码后,,答案分别为 ,异或和为 。
本题目采用捆绑测试。
子任务编号 | 时间限制 | 特殊性质 | 分值 | |||
---|---|---|---|---|---|---|
1 秒 | 样例 | |||||
2 秒 |
对于 数据,满足 $1\le k\le 16,1\le q\le 3000,0\le p_i<998244353,1\le a_i\le 2^{15},0\le l_i\le r_i< 2^k,0\le x_{i,j}< 2^k,t\in\{0,1\},0\le seed\le 50007$。保证 。
本题输入输出量大,请使用较快的输入输出方式。