TouchStone
  请登录后使用
登录 注册
距离CSP第一轮: ??天 距离CSP第二轮: ??天 距离NOIP还有: ??天
 系统首页  练习题库  考试列表  判题结果  信息发布  解题排行
  • 首页
  • 题库
  • P3350
  • 题目
  • P3350【THOI2015】平方运算
    限制 : 时间限制 : 1000 MS   空间限制 : 65536 KB
    问题描述

    小H是一位勤奋的中学生,他的理想是进入自己心仪的大学学习计算机专业。为了实现这一目标,他从小就开始认真学习信息学竞赛的基础知识。
    今天,小H学习了平方运算。为了检验自己是否熟练掌握了平方运算,小H决定给自己出一道题。小H有一个长度为N的序列{X1,X2,...,XN}。小H会时不时地取出序列中的一段连续区间[l,r],并将其中的每一个数改为原数值的平方对p取模的结果,即
    任意的i∈[l,r],Xi<-(Xi*Xi) mod p
    其中,p为某个给定的数。为了检验自己的运算是否正确,小H还会时不时地想要知道序列中某一段连续区间[l,r]内所有的数的和是多少。
    但是,小H现在并没有标准答案。所以,他向你求助,希望你编写一个程序,帮他计算出每次想要知道的区间内的数的总和。

    输入格式

    第一行有三个整数N,M,p,分别代表序列的长度、平方操作与询问操作的总次数以及在平方操作中要模的数。
    接下来一行N个数代表一开始的序列{X1,X2,...,XN}。
    接下来M行,每行三个整数op,l,r。其中op代表本次操作的类型。若op=0,代表这是一次平方操作,平方的区间为[l,r];如果op=1,代表这是一次询问操作,询问的区间为[l,r]。

    输出格式

    对于每次的询问操作,输出一行代表这段区间类数的总和。
    注意:答案没有对任何数取模

    样例输入

    样例1:
    3 3 11
    1 2 3
    1 1 3
    0 1 3
    1 1 3
    样例2:
    3 3 3
    0 1 2
    1 1 3
    0 1 3
    1 1 3

    样例输出

    样例1:
    6
    14
    样例2:
    3
    2

    提示

    数据范围:
    对于100%的数据,i,Xi∈[0,p),l,r∈[1,N]。
    N,M,p的范围详见下表: