Description

Informatikverbindetdichundmich.
信息将你我连结。B君希望以维护一个长度为n的数组,这个数组的下标为从1到n的正整数。一共有m个操作,可以
分为两种:0 l r表示将第l个到第r个数(al,al+1,…,ar)中的每一个数ai替换为c^ai,即c的ai次方,其中c是
输入的一个常数,也就是执行赋值ai=c^ai1 l r求第l个到第r个数的和,也就是输出:sigma(ai),l<=i<=rai因为
这个结果可能会很大,所以你只需要输出结果mod p的值即可。

Input

第一行有三个整数n,m,p,c,所有整数含义见问题描述。
接下来一行n个整数,表示a数组的初始值。
接下来m行,每行三个整数,其中第一个整数表示了操作的类型。
如果是0的话,表示这是一个修改操作,操作的参数为l,r。
如果是1的话,表示这是一个询问操作,操作的参数为l,r。
1 ≤ n ≤ 50000, 1 ≤ m ≤ 50000, 1 ≤ p ≤ 100000000, 0 < c <p, 0 ≤ ai < p

Output

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

Sample Input

4 4 7 2
1 2 3 4
0 1 4
1 2 4
0 1 4
1 1 3

Sample Output

0
3

HINT

 鸣谢多名网友提供正确数据,已重测!

Source

这题不知道欧拉函数 降幂公式真没法做 全程感谢tgptp&zyy的支持 才让辣鸡蒟蒻我做完了这题

首先欧拉函数是<n的所有正整数里于n互质的有多少个 有个性质在于如果n!=2那么一定函数值是偶数也是后面保证复杂度的前提

公式

利用这个公式记得只有在>=phi[p]的时候才成立 但是记得某个巨佬里提到过如果不判断这个条件也只会在n=6的时候失效所以数据可以不判断

A^B(mod p)≡A^(b%φ(p)+φ(p)) 因为上面提到的性质 所以这个φ(p)最多递归Log次 注意当为1的时候也需要递归 具体原因在bzoj的discuss里面提到过 为什么这个是对的 直接搞指数取mod为什么不对 因为我要取的mod不是p而是φ(p)或者φ(φ(p)) 那么这样的话做法就类似之前的一个cf题 每次做的时候判断这个区间是否已经被做了log次了如果是这样 好这个区间答案不会再改变了 否则暴力改下去 复杂度均摊log(n)算上一共是n*log(n)个区间 还有每次快速幂的log 一共是log^3我的尝数不优秀直接tle了那么考虑怎么优化  看了看题解我可以前 2^16 分一组 后2^16分一组 因为底数都是相同的所以可以直接预处理出来做到近似o(1)回答

n*log(n)^2

 

n*log(n)^3


 

分类: 数学线段树

elijahqi

辣鸡蒟蒻一枚qwq 欢迎加qq qwq 2922945330

发表评论