#ZJOI2022D. 拉面

拉面

题目背景

忍,爱丽丝,绫和阳子一众千辛万苦地总算出好了第一试,按原先计划,可怜会出第二试。
“不好了,可怜给我发消息说她降落后被拉去隔离 3030 天了,没有电脑,出不了题”,绫突然收到了不幸的消息。
“那咋办?没 idea 了,编不出来了啊!”众人慌作一团。
看了看日期,离 ZJOI 还有一周。
欲知后事如何,请看下回分解。

题目描述

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

有一天她去吃拉面,她发现拉面师傅为她拉的是一个长度为 nn 的面条,nn 保证是偶数,一开始第 ii 个位置调料的数量是 aia_i

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

  1. 将面条对折,面条的长度会变成 n2\frac n 2,第 ii 个位置的调料数量会变为原来第 ii 个位置的调料与第 ni+1n - i + 1 个位置的调料数量之和,如果新面条第 ii 个位置的调料数量为 bib_i,那么满足 bi=ai+ani+1b_i = a_i + a_{n - i + 1}
  2. 将面条拉回原来的长度 nn,每个位置会变为两个位置,并且调料数量会均分,如果现在第 ii 个位置的调料数量是 aia_i^{\prime},那么 $a_i^{\prime} = \frac 1 2 \times b_{\lceil \frac i 2 \rceil}$。

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

输入格式

从文件 noodle.in 中读入数据。

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

接下来输入 TT 组数据,每组数据包含两行。

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

第二行输入 nn 个非负整数,第 ii 个整数 aia_i 代表初始面条第 ii 个位置的调料数量。

为了避免大量的输入与输出,qq 个寻问由我们提供的一个生成器生成。具体地,我们提供一个由 C++ 书写的代码框架 noodle_template.cpp 供选手使用,见附录,同时在这里我们做一定量的说明:

首先我们从数据中依次读入两个 3232 位整型变量 test, Ttest,~T,一个无符号 6464 位长整型变量 seedseed。接下来循环 TT 次,代表 TT 组数据。

在每次循环中,我们对一组数据进行计算。首先以此读入三个 3232 位整型变量 n, q, xn,~q,~x,一个 6464 位整型变量 kmaxk_{max}。接下来读入 nn3232 位整型变量放入数组 a1, ,ana_1,~\dots,a_n 中。

接下来是生成 qq 个询问的部分,每次调用 rd() 函数,将 seedseed 作为引用参数传入,将返回值(返回值位无符号 6464 位长整型)对 kmaxk_{max} 取模的结果作为该询问的参数 kk,注意到 seedseed 也会被修改。

输出格式

输出到文件 noodle.out 中。

输出 TT 行,每行一个整数代表该组数据的答案。具体地,假设该组数据有 qq 个询问,令第 ii 个询问答案为 AnsiAns_i,那么你需要输出 i=1q(Ansi×i)\oplus_{i = 1}^q (Ans_i \times i)注意这里不需要取模\oplus 指按位异或运算符。

0 2 13
4 2 1 3
1 4 2 3
6 2 3 3
6 2 5 3 1 4
5
499122191

第一组测试数据中,{ai}\{a_i\} 初始为 {1, 4, 2, 3}\{1,~4,~2,~3\}
操作一次后为 {2, 2, 3, 3}\{2,~2,~3,~3\}
操作两次后为 {52, 52, 52, 52}\{\frac 5 2,~\frac 5 2,~\frac 5 2,~\frac 5 2\}

其中生成询问为:
询问位置:x=1x = 1
第一个询问:k=0, ax=1k = 0,~a_x = 1
第二个询问:k=1, ax=2k = 1,~a_x = 2

答案为 (1×1)(2×2)=41=5(1 \times 1) \oplus (2 \times 2) = 4 \oplus 1 = 5.

第二组测试数据中,{ai}\{a_i\} 初始为 {6, 2, 5, 3, 1, 4}\{6,~2,~5,~3,~1,~4\}
操作一次后为 {5, 5, 32, 32, 4, 4}\{5,~5,~\frac 3 2,~\frac 3 2,~4,~4\}
操作两次后为 $\{\frac 9 2,~\frac 9 2,~\frac 9 2,~\frac 9 2,~\frac 3 2,~\frac 3 2\}$。

其中生成询问为:
询问位置:x=3x = 3
第一个询问 k=2, ax=92k = 2,~a_x = \frac 9 292499122181 (mod 998244353)\frac 9 2 \equiv 499122181~(\bmod~998244353)
第二个询问 k=0, ax=5k = 0,~a_x = 5

答案为 $(499122181 \times 1) \oplus (5 \times 2) = 499122181 \oplus 10 = 499122191$。

输入输出数据 2

见下发文件中的 noodle_ex2.innoodle_ex2.ans

数据范围与提示

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

注意,对于样例,测试点编号 testtest00

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

测试点编号 n\sum n \le q\sum q \le kmaxk_{max} \le 特殊限制
11 500500
22 2×1062 \times 10^6 1010
33 101810^{18} n=2kn = 2^k
44 5050
5, 65,~6 150150
77 2×1062 \times 10^6 n=98304n = 98304
8, 98,~9 500500
10, 1110,~11 5×1035 \times 10^3 2×1062 \times 10^6
12, 1312,~13 2×1062 \times 10^6 5050
14, 15, 1614,~15,~16 10610^6 10510^5
17, 1817,~18 2×1062 \times 10^6 2×1072 \times 10^7
19, 2019,~20 5×1075 \times 10^7

附录

noodle_template.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.
			*/
		}
	}
}