A6020 | $「2017 山东三轮集训 Day4」Mid$

时间限制2s

内存限制512MB

通过 / 提交0/0

题目描述

JOHNKRAM 在冬令营的时候被 wys 的卡常题坑了。他表示非常不爽，于是决定也出一道卡常题来祸害人。 有一个多重集，初始时为空。JOHNKRAM 进行了 $ n $ 次操作，每次操作往多重集内插入一个整数。第 $ i(1 \leq i \leq n) $ 次操作完之后他会问你这个多重集内第 $ \frac{n + 1}{2} $ 小的数是多少。为了防止你的工作量过大，你只需要把每次询问的答案异或起来得到的值告诉他即可。

第一行两个整数 $ n $ 和 $ a_1 $，指操作的次数和第一次操作插入的数。 接下来插入的数按如下方法生成：$ a_i = (1714636915 \times a_{i - 1} + 1681692777) \times (846930886 \times \text{ans}_{i - 1} + 1804289383) \bmod 1000000007 $。其中 $ \text{ans}_{i - 1} $ 指第 $ i - 1 $ 次询问的答案。

输出一个整数，表示所有 $ \text{ans}_i (1 < i < n) $ 异或得到的值。

输入 #1

10 1

输出 #1

943960841

C++ 编辑器

输入

输出