P3747 [六省联考2017]相逢是问候

    • 327通过
    • 2.5K提交
  • 题目提供者 SakuraDance
  • 评测方式 云端评测
  • 标签 同余,中国剩余定理 素数判断,质数,筛法 线段树 各省省选 2017 O2优化 高性能
  • 难度 NOI/NOI+/CTSC
  • 时空限制 2000ms / 512MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题目描述

    Informatik verbindet dich und mich.

    信息将你我连结。

    B 君希望以维护一个长度为 n 的数组,这个数组的下标为从 1 到 n 的正整数。

    一共有 m 个操作,可以分为两种:

    • 0 l r 表示将第 l 个到第 r 个数( $a_l,a{l+1},...a_r$)中的每一个数 $a_i$ 替换为 $c^{a_i}$,即 c 的 $a_i$ 次方,其中 c 是输入的一个常数,也就是执行赋值

    $a_i = c^{a_i}$

    • 1 l r 求第 l 个到第 r 个数的和,也就是输出:

    $\sum_{i=l}^{r}a_i$

    因为这个结果可能会很大,所以你只需要输出结果 mod p 的值即可。

    输入输出格式

    输入格式:

    第一行有四个整数 $n, m, p, c$,所有整数含义见问题描述。
    接下来一行 $n$ 个整数,表示 $a$ 数组的初始值。
    接下来 $m$ 行,每行三个整数,其中第一个整数表示了操作的类型。

    • 如果是 $0$ 的话,表示这是一个修改操作,操作的参数为 $l, r$。
    • 如果是 $1$ 的话,表示这是一个询问操作,操作的参数为 $l, r$。

    输出格式:

    对于每个询问操作,输出一行,包括一个整数表示答案 mod p 的值。

    输入输出样例

    输入样例#1: 复制
    4 4 7 2
    1 2 3 4
    0 1 4
    1 2 4
    0 1 4
    1 1 3
    输出样例#1: 复制
    0
    3

    说明

    • 对于 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。