A6590. 「ZJOI2022」面条

九条可怜是一个喜欢吃拉面的女孩子。

有一天她去吃拉面，她发现拉面师傅为她拉的是一个长度为 $n$ 的面条，$n$ 保证是偶数，一开始第 $i$ 个位置调料的数量是 $a_i$。

如下过程称为一次 “拉面”：

1. 将面条对折，面条的长度会变成 $\frac{n}{2}$，第 $i$ 个位置的调料数量会变为原来第 $i$ 个位置的调料与第 $n - i + 1$ 个位置的调料数量之和，如果新面条第 $i$ 个位置的调料数量为 $b_i$，那么满足 $b_i = a_i + a_{n - i + 1}$。
2. 将面条拉回原来的长度 $n$，每个位置会变为两个位置，并且调料数量会均分，如果现在的第 $i$ 个位置的调料数量是 $a'_i$，那么 $a'_i = \frac{1}{2} \times b_{\left\lceil \frac{i}{2} \right\rceil}$。

现在对于一个固定的 $x$，你需要回答 $q$ 个询问，每次面条经过 $k$ 次 “拉面” 后，第 $x$ 个位置的调料数量。你只需要求出答案对 $998244353$ 取模的结果。具体地，即如果答案的最简分数表示为 $\frac{a}{b}$，输出 $a \times b^{-1} \bmod 998244353$。

第一行输入三个正整数 $test, T, seed$，代表测试点编号，数据组数和生成种子。

接下来输入 $T$ 组数据，每组数据包含两行。

第一行输入四个正整数 $n, q, x, k_{\mathrm{max}}$，代表这组数据中面条的长度，询问的个数，询问的位置和生成询问中 $k$ 的上限。

第二行输入 $n$ 个非负整数，第 $i$ 个整数 $a_i$ 代表初始面条第 $i$ 个位置的调料数量。

为了避免大量的输入与输出，$q$ 个询问由我们提供的一个生成器生成。具体地，我们提供一个由 C++ 书写的代码框架 noodle_template.cpp 供选手使用，见本段最后，同时在这里我们做一定量的说明：

首先我们从数据中依次读入两个 $32$ 位整型变量 $\mathit{test}, T$，一个无符号 $64$ 位长整型变量 $\mathit{seed}$。接下来循环 $T$ 次，代表 $T$ 组数据。

在每次循环中，我们对一组数据进行计算。首先依次读入三个 $32$ 位整型变量 $n, q, x$，一个 $64$ 位整型变量 $k_{\mathrm{max}}$。接下来读入 $n$ 个 $32$ 位整型变量放入数组 $a_1, \ldots, a_n$ 中。

接下来是生成 $q$ 个询问的部分，每次调用 rd() 函数，将 $\mathit{seed}$ 作为引用参数传入，将返回值（返回值为无符号 $64$ 位长整型）对 $k_{\mathrm{max}}$ 取模的结果作为该次询问的参数 $k$，注意到 $\mathit{seed}$ 也会被修改。



```cpp
#include <bits/stdc++.h>
using namespace std;

unsigned long long rd (unsigned long long &x) {
x ^= (x << 13);
x ^= (x >> 7);
x ^= (x << 17);
return x;
}

int main () {
int test, T;
unsigned long long seed;
scanf("%d%d%llu", &test, &T, &seed);
for (int Case = 1; Case <= T; Case ++) {
int n, q, x;
long long k_max;
scanf("%d%d%d%lld", &n, &q, &x, &k_max);
vector<int> a(n + 1);
for (int i = 1; i <= n; i ++) {
scanf("%d", &a[i]);
}
for (int i = 1; i <= q; i ++) {
long long k = rd(seed) % k_max;
/∗
Code your solution here.
∗/
}
}
}
```

输出 $T$ 行，每行一个整数代表该组数据的答案。具体地，假设该组数据有 $q$ 个询问，令第 $i$ 个询问的答案为 $\mathrm{Ans}_i$，那么需要你输出 $\bigoplus_{i = 1}^q (\mathrm{Ans}_i \cdot i)$，**注意这里不需要取模**。$\bigoplus$ 指按位异或运算符。

对于所有测试点：保证 $T \le 10$，$\sum n \le 2 \times {10}^6$，$\sum q \le 5 \times {10}^7$，$k_{\mathrm{max}} \le {10}^{18}$，$1 \le x \le n$，$0 \le a_i < 998244353$，$0 \le \mathit{seed} \le 2^{60} - 1$，保证 $n$ 是偶数。

注意，对于样例，测试点编号 $\mathit{test}$ 为 $0$。

每个测试点的具体限制见下表：

| 测试点编号 | $\sum n \le$ | $\sum q \le$ | $k_{\mathrm{max}} \le $ | 特殊限制 |
|:-:|:-:|:-:|:-:|:-:|
| $1$ | $500$ | $500$ | $500$ | 无 |
| $2$ | $2 \times {10}^6$ | $2 \times {10}^6$ | $10$ | 无 |
| $3$ | $2 \times {10}^6$ | $2 \times {10}^6$ | ${10}^{18}$ | $n = 2^k$ |
| $4$ | $50$ | $50$ | ${10}^{18}$ | 无 |
| $5 \sim 6$ | $150$ | $150$ | ${10}^{18}$ | 无 |
| $7$ | $2 \times {10}^6$ | $2 \times {10}^6$ | ${10}^{18}$ | $n = 98304$ |
| $8 \sim 9$ | $500$ | $500$ | ${10}^{18}$ | 无 |
| $10 \sim 11$ | $5 \times {10}^3$ | $2 \times {10}^6$ | ${10}^{18}$ | 无 |
| $12 \sim 13$ | $2 \times {10}^6$ | $50$ | ${10}^{18}$ | 无 |
| $14 \sim 16$ | ${10}^6$ | ${10}^5$ | ${10}^{18}$ | 无 |
| $17 \sim 18$ | $2 \times {10}^6$ | $2 \times {10}^7$ | ${10}^{18}$ | 无 |
| $19 \sim 20$ | $2 \times {10}^6$ | $5 \times {10}^7$ | ${10}^{18}$ | 无 |