#PQJ922x4010. QOJ 922_4010

    ID: 3059 传统题 4000ms 1024MiB 尝试: 0 已通过: 0 难度: 省选/NOI- 上传者: 标签>来源:qoj.ac章节练习数据:双算对拍权威答案来源:省选赛事:ZJOI 2022模拟

QOJ 922_4010

ZJOI 2022 第二试 面条(noodle) 面条(noodle) 【题目背景】 忍,爱丽丝,绫和阳子一众千辛万苦地总算出好了第一试,按原先计划,可怜会出第二试。 “不好了,可怜给我发信息说她降落后被拉去隔离30 天了,没有电脑,出不了题”,绫突然收 到了不幸的消息。 “那咋办?没idea了,编不出来了啊!”众人慌作一团。 看了看日期,离ZJOI还有一周。 欲知后事如何,请看下回分解。 【题目描述】 九条可怜是一个喜欢吃拉面的女孩子。 有一天她去吃拉面,她发现拉面师傅为她拉的是一个长度为n 的面条,n 保证是偶数,一开始 第i 个位置调料的数量是ai。 如下过程称为一次“拉面”:

  1. 将面条对折,面条的长度会变成 n 2 ,第i 个位置的调料数量会变为原来第i 个位置的调料 与第n −i + 1 个位置的调料数量之和,如果新面条第i 个位置的调料数量为bi,那么满足 bi = ai + an−i+1。
  2. 将面条拉回原来的长度n,每个位置会变为两个位置,并且调料数量会均分,如果现在的第i 个位置的调料数量是a′ i,那么a′ i = 1 2 × b⌈i 2 ⌉。 现在对于一个固定的x,你需要回答q 个询问,每次面条经过k 次“拉面”后,第x 个位置的 调料数量。你只需要求出答案对998 244 353 取模的结果。具体地,即如果答案的最简分数表示为 a b ,输出a × b−1 mod 998 244 353。 【输入格式】 从文件noodle.in 中读入数据。 第一行输入三个正整数test, T, seed,代表测试点编号,数据组数和生成种子。 接下来输入T 组数据,每组数据包含两行。 第一行输入四个正整数n, q, x, kmax,代表这组数据中面条的长度,询问的个数,询问的位置和 生成询问中k 的上限。 第二行输入n 个非负整数,第i 个整数ai 代表初始面条第i 个位置的调料数量。 为了避免大量的输入与输出,q 个询问由我们提供的一个生成器生成。具体地,我们提供一个 由C++书写的代码框架noodle template.cpp 供选手使用,见附录,同时在这里我们做一定量的说 明: 首先我们从数据中依次读入两个32 位整型变量test, T,一个无符号64 位长整型变量seed。接 下来循环T 次,代表T 组数据。 在每次循环中,我们对一组数据进行计算。首先依次读入三个32 位整型变量n, q, x,一个64 位 整型变量kmax。接下来读入n 个32 位整型变量放入数组a1, · · · , an 中。 第2 页 共9 页

ZJOI 2022 第二试 面条(noodle) 接下来是生成q 个询问的部分,每次调用rd() 函数,将seed 作为引用参数传入,将返回值(返 回值为无符号64 位长整型)对kmax 取模的结果作为该次询问的参数k,注意到seed 也会被修改。 【输出格式】 输出到文件noodle.out 中。 输出T 行,每行一个整数代表该组数据的答案。具体地,假设该组数据有q 个询问,令第i 个 询问的答案为Ansi,那么需要你输出⊕q i=1(Ansi · i),注意这里不需要取模。⊕指按位异或运算符。 【样例输入】 见下发文件中的noodle ex1.in和noodle ex2.in。 【样例输出】 见下发文件中的noodle ex1.ans和noodle ex2.ans。 第3 页 共9 页

ZJOI 2022 第二试 面条(noodle) 【数据范围与提示】 对于所有测试点:保证T ≤10, P n ≤2 × 106, P q ≤5 × 107, kmax ≤1018, 1 ≤x ≤n, 0 ≤ai < 998 244 353, 0 ≤seed ≤260 −1,保证n 是偶数。 注意,对于样例,测试点编号test 为0。 每个测试点的具体限制见下表: 测试点编号 P n ≤ P q ≤ kmax ≤ 特殊限制 1 500 500 500 无 2 2 × 106 2 × 106 10 无 3 2 × 106 2 × 106 1018 n = 2k 4 50 50 1018 无 5, 6 150 150 1018 无 7 2 × 106 2 × 106 1018 n = 98 304 8, 9 500 500 1018 无 10, 11 5 × 103 2 × 106 1018 无 12, 13 2 × 106 50 1018 无 14, 15, 16 106 105 1018 无 17, 18 2 × 106 2 × 107 1018 无 19, 20 2 × 106 5 × 107 1018 无 【样例解释】 对于样例1: 第一组测试数据中,{ai} 初始为{1, 4, 2, 3}。 操作一次后为{2, 2, 3, 3}。 操作两次后为{ 5 2, 5 2, 5 2, 5 2}。 其中生成询问为: 询问位置:x = 1; 第一个询问:k = 0,ax = 1; 第二个询问:k = 1,ax = 2; 答案为(1 × 1) ⊕(2 × 2) = 4 ⊕1 = 5。 第二组测试数据中,{ai} 初始为{6, 2, 5, 3, 1, 4}。 操作一次后为{5, 5, 3 2, 3 2, 4, 4}。 操作两次后为{ 9 2, 9 2, 9 2, 9 2, 3 2, 3 2}。 其中生成询问为: 询问位置:x = 3; 第一个询问k = 2,ax = 9 2,9 2 ≡499122181 (mod 998244353); 第二个询问k = 0,ax = 5; 答案为(499122181 × 1) ⊕(5 × 2) = 499122181 ⊕10 = 499122191。 第4 页 共9 页

ZJOI 2022 第二试 面条(noodle) 【附录】 #include <b i t s / 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%l l u ” , &test , &T, &seed ) ; for ( int Case = 1; Case <= T; Case ++) { int n , q , x ; long long k max ; scanf ( ”%d%d%d%l l d ” , &n , &q , &x , &k max ) ; vector 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 s o l u t i o n here . ∗/ } } } 第5 页 共9 页