A6020. 「2017 山东三轮集训 Day4」Mid
编程题
提高+/省选-
知识点
题目描述
JOHNKRAM 在冬令营的时候被 wys 的卡常题坑了。他表示非常不爽，于是决定也出一道卡常题来祸害人。
有一个多重集，初始时为空。JOHNKRAM 进行了 $ n $ 次操作，每次操作往多重集内插入一个整数。第 $ i(1 \leq i \leq n) $ 次操作完之后他会问你这个多重集内第 $ \frac{n + 1}{2} $ 小的数是多少。为了防止你的工作量过大，你只需要把每次询问的答案异或起来得到的值告诉他即可。
有一个多重集，初始时为空。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 $ 次询问的答案。
接下来插入的数按如下方法生成：$ 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
说明/提示
对于 $ 30\% $ 的数据，$ n \leq 3 \times 19 ^ 3 $；
对于 $ 50\% $ 的数据，$ n \leq 1 \times 10 ^ 6 $；
对于 $ 100\% $ 的数据，$ 1 \leq n \leq 3 \times 10 ^ 7, 1 \leq a_1 < 1000000007 $。
对于 $ 50\% $ 的数据，$ n \leq 1 \times 10 ^ 6 $；
对于 $ 100\% $ 的数据，$ 1 \leq n \leq 3 \times 10 ^ 7, 1 \leq a_1 < 1000000007 $。