#PQJ388x3264. QOJ 388_3264

    ID: 2938 传统题 4000ms 512MiB 尝试: 0 已通过: 0 难度: 省选/NOI- 上传者: 标签>来源:qoj.ac章节练习数据:双算对拍权威答案来源:省选赛事:六省联合省选2017线段树模拟

QOJ 388_3264

2017 年全国青少年信息学奥林匹克竞赛上海市代表队选拔 第一试相逢是问候(verbinden) 相逢是问候(verbinden) 【问题描述】 Informatik verbindet dich und mich. 信息将你我连结。 B 君希望以维护一个长度为n 的数组,这个数组的下标为从1 到n 的正整数。 一共有m 个操作,可以分为两种: 0 l r 表示将第l 个到第r 个数(al, al+1, . . . , ar)中的每一个数ai 替换为cai,即c 的ai 次方,其中c 是输入的一个常数,也就是执行赋值 ai = cai 1 l r 求第l 个到第r 个数的和,也就是输出: r∑ i=l ai 因为这个结果可能会很大,所以你只需要输出结果modp 的值即可。 【输入格式】 从文件verbinden.in 中读入数据。 第一行有三个整数n, m, p, c,所有整数含义见问题描述。 接下来一行n 个整数,表示a 数组的初始值。 接下来m 行,每行三个整数,其中第一个整数表示了操作的类型。 如果是0 的话,表示这是一个修改操作,操作的参数为l, r。 如果是1 的话,表示这是一个询问操作,操作的参数为l, r。 【输出格式】 输出到文件verbinden.out 中。 对于每个询问操作,输出一行,包括一个整数表示答案modp 的值。 【样例1 输入】 4 4 7 2 1 2 3 4 0 1 4 1 2 4 0 1 4 1 1 3 第4 页 共9 页

2017 年全国青少年信息学奥林匹克竞赛上海市代表队选拔 第一试相逢是问候(verbinden) 【样例1 输出】 0 3 【样例2 输入】 1 40 19910626 2 0 0 1 1 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 0 1 1 第5 页 共9 页

2017 年全国青少年信息学奥林匹克竞赛上海市代表队选拔 第一试相逢是问候(verbinden) 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 【样例2 输出】 1 2 4 16 65536 11418102 18325590 13700558 13700558 13700558 13700558 13700558 13700558 13700558 13700558 13700558 13700558 13700558 13700558 13700558 【样例3】 见选手目录下的verbinden/verbinden3.in 与verbinden/verbinden3.ans。 第6 页 共9 页

2017 年全国青少年信息学奥林匹克竞赛上海市代表队选拔 第一试相逢是问候(verbinden) 【子任务】 • 对于0% 的测试点,和样例一模一样; • 对于另外10% 的测试点,没有修改; • 对于另外20% 的测试点,每次修改操作只会修改一个位置(也就是l = r),并 且每个位置至多被修改一次; • 对于另外10% 的测试点,p = 2; • 对于另外10% 的测试点,p = 3; • 对于另外10% 的测试点,p = 4; • 对于另外20% 的测试点,n ≤100, m ≤100; • 对于100% 的测试点,1 ≤n ≤50000, 1 ≤m ≤50000, 1 ≤p ≤100000000, 0 < c < p, 0 ≤ai < p。 第7 页 共9 页