宁夏公路建设管理局网站,宁夏建设教育协会网站,wordpress替换google字体,万联芯城网站建设gym 102875A – Array
题意#xff1a;
对于一个数组a#xff0c;以及数p#xff0c; q个操作 1.对于区间[l,r]#xff0c;里面所有数k 2.对于区间[l,r]#xff0c;里面所有数 * k 3.对于区间[l,r]#xff0c;里面所有数变成k次幂 4.对于区间[l,r]#xff0c;输出里面…gym 102875A – Array
题意
对于一个数组a以及数p q个操作 1.对于区间[l,r]里面所有数k 2.对于区间[l,r]里面所有数 * k 3.对于区间[l,r]里面所有数变成k次幂 4.对于区间[l,r]输出里面所有数k次幂的和 5.对于区间[l,r]输出里面所有数的乘积 操作4和5的结果mod p 1n1e5 2p30 0a1e9 1q1e5 注我们规定00 1
题解
参考题解 参考题解 第一个题解的方法很妙因为p的范围很小所以可以直接用线段树来维护每个区间值为x的数有多少个f数组用来记录每个数转移成了什么数 num[root1][f[root][i]] num[root1][i] 第二个方法在计算快速幂时用欧拉降幂来优化下常数 4月26再看这题 在刷了很多树之后有些感觉。。但感觉让自己写还是写不出 num[root][i]以root为根的子树中有多少个i f[root][i] 表示以root为根的子树中原本的i转移成了什么数 因为p很小所以可以将mod值和pow值记得取模提前求好 代码很妙思路也很好是个好题
代码
#includebits/stdc.h
using namespace std;
#define G if(ipie)if(fread(ipbuf,1,SZ,stdin))
#define ri register int
#define iv inline void
using namespace std;
const int SZ119;
char buf[SZ],*iebufSZ,*ipie-1;
inline int in(){G;while(*ip-)G;ri x*ip15;G;while(*ip-){x*10;x*ip15;G;}return x;
}
const int N1e55;
int p;
int num[N*4][35],f[N*4][35];
int tmp[35];
void push_down(int root){for(int i0;ip;i){tmp[i]num[root1][i];num[root1][i]0;} for(int i0;ip;i){num[root1][f[root][i]]tmp[i];}for(int i0;ip;i){tmp[i]num[root1|1][i];num[root1|1][i]0;}for(int i0;ip;i){num[root1|1][f[root][i]]tmp[i];}for(int i0;ip;i){f[root1][i]f[root][f[root1][i]];f[root1|1][i]f[root][f[root1|1][i]];}for(int i0;ip;i)f[root][i]i;
}
int a[N];
void build(int l,int r,int root){for(int i0;ip;i)f[root][i]i;if(lr){num[root][a[l]]1;return ;}int midlr1;build(l,mid,root1);build(mid1,r,root1|1);for(int i0;ip;i)num[root][i]num[root1][i]num[root1|1][i];
}
int quik(int a,int b){int ans1;for(;b;b1,aa*a%p)if(b1)ansans*a%p;return ans;}
int mod[N];
int qpow[35];
/*
num[root][i]以root为根的子树中有多少个i
f[root][i] 表示以root为根的子树中原本的i转移成了什么数
*/
void update(int l,int r,int root,int ql,int qr,int op,int v){if(lqlrqr){if(op2){//mulfor(int i0;ip;i){tmp[i]num[root][i];num[root][i]0;}for(int i0;ip;i){num[root][mod[i*v]]tmp[i];f[root][i]mod[f[root][i]*v];}}else if(op1){//addfor(int i0;ip;i){tmp[i]num[root][i];num[root][i]0;}for(int i0;ip;i){num[root][mod[(iv)]]tmp[i];f[root][i]mod[(f[root][i]v)];}}else if(op3){//^kfor(int i0;ip;i){tmp[i]num[root][i];num[root][i]0;}for(int i0;ip;i){num[root][qpow[i]]tmp[i];f[root][i]qpow[f[root][i]];}}return ;}push_down(root);int midlr1;if(midql)update(l,mid,root1,ql,qr,op,v);if(midqr)update(mid1,r,root1|1,ql,qr,op,v);for(int i0;ip;i)num[root][i]num[root1][i]num[root1|1][i];
}
int ans[35];
void query(int l,int r,int root,int ql,int qr){if(lqlrqr){for(int i0;i30;i)ans[i]num[root][i];return ;}push_down(root);int midlr1;if(midql)query(l,mid,root1,ql,qr);if(midqr)query(mid1,r,root1|1,ql,qr);
}
int main()
{int n;nin(),pin();for(int i1;in;i)a[i]in(),a[i]%p;for(int i0;i35*35;i)mod[i]i%p;build(1,n,1);int q;qin();while(q--){int op,l,r,k;opin(),lin(),rin(),kin();if(op2)k%p;else if(op3){for(int i0;ip;i)qpow[i]quik(i,k);}if(op3)update(1,n,1,l,r,op,k);else {for(int i0;ip;i)ans[i]0;query(1,n,1,l,r);if(op4){int sum0;for(int i0;ip;i)sum(sumquik(i,k)*ans[i])%p;printf(%d\n,sum);}else {int sum1;for(int i0;ip;i)sumsum*quik(i,ans[i])%p;printf(%d\n,sum);}}}return 0;
}
