【GDOI2018模拟7.9】相逢是问候

Description

Solution

首先需要了解欧拉定理的一个拓展： ax≡axmodϕ(P)+ϕ(P) (modP) （注：该公式只有在 x≥ϕ(P) 时成立，证明戳这里） 有了这个定理我们就可以很好地解决这道题，首先可以发现，操作几次之后，指数会变得非常大，而套用公式可以降低指数。同时我们可以发现，每一次操作都会模不同的数，套上公式可以发现，直接对指数的取模，模的值为若干个 ϕ 套在一起。同时可以发现，大概在套了26次以后，即对同一个位置操作26次之后，这个指数就会变成一个常值。我们可以预处理出每一个位置在进行若干次后的值，因为在26次之后的操作都将会是一个定值，问题就转化为对于某一些区间进行操作，每一次操作对应会有固定的值，而当某一整个区间的每一个元素操作数大于26次后，就可以直接跳过这个区间。 因为在预处理的时候需要用到快速幂，但是快速幂带了一个log，弄在一起会超时，所以要压掉（黑科技get）。

Code

#include<string.h> #include<algorithm> #include<stdio.h> #include<math.h> #include<iostream> using namespace std; #define fo(i,a,b) for(i=a;i<=b;i++) #define fd(i,a,b) for(i=a;i>=b;i--) typedef long long ll; const int N=5e4+5; const ll Z=1<<14;//1<<16; struct arr{ ll x;int sum; }t[N*3]; ll P[30],C[N][30],Q1[Z][30],Q2[Z][30]; ll cz,l,r,mo,c,a[N],ans,ci; int n,m,i,j,k,sum,len; char re,ch[20]; void read(ll &x){ for(re=getchar();re<'0'||re>'9';re=getchar()); x=re-48; for(re=getchar();re>='0'&&re<='9';re=getchar()) x=x*10+re-48; } void write(ll x){ len=0;memset(ch,0,sizeof(ch)); for(;x;x/=10) ch[++len]=x+'0'; for(;len;len--) putchar(ch[len]); putchar('\n'); } ll phi(ll x){ ll phi=x,t=x,i; for(i=2;i*i<=t;i++) if(!(t%i)){ phi=phi/i*(i-1); while(!(t%i)) t/=i; } phi=(t>1)?phi/t*(t-1):phi; return phi; } ll ksm(ll x,ll y,ll mo){ ll z=1; for(;y;y/=2,x=x*x%mo+(x*x>=mo)*mo)if(y&1)z=z*x%mo+(z*x>=mo)*mo; return z; } void make(int l,int r,int wz){ if(l==r){t[wz].x=a[l]; return;} int mid=(l+r)/2; make(l,mid,wz*2);make(mid+1,r,wz*2+1); t[wz].x=(t[wz*2].x+t[wz*2+1].x)%mo; } void change(int l,int r,int wz,int x,int y){ if(t[wz].sum>=sum) return; if(l==r){t[wz].x=C[l][++t[wz].sum];return;} int mid=(l+r)/2; if(y<=mid) change(l,mid,wz*2,x,y); else if(x>mid) change(mid+1,r,wz*2+1,x,y); else{ change(l,mid,wz*2,x,mid); change(mid+1,r,wz*2+1,mid+1,y); } t[wz].x=(t[wz*2].x+t[wz*2+1].x)%mo; t[wz].sum=(t[wz*2].sum<t[wz*2+1].sum)?t[wz*2].sum:t[wz*2+1].sum; } void ask(int l,int r,int wz,int x,int y){ if(l==x&&r==y){ans=(ans+t[wz].x)%mo;return;} int mid=(l+r)/2; if(y<=mid) ask(l,mid,wz*2,x,y); else if(x>mid) ask(mid+1,r,wz*2+1,x,y); else{ ask(l,mid,wz*2,x,mid); ask(mid+1,r,wz*2+1,mid+1,y); } } void pre(){ P[0]=mo;while(P[sum]!=1) P[sum+1]=phi(P[sum]),sum++;P[++sum]=1; fo(i,0,Z-1)fo(j,1,sum) Q1[i][j]=ksm(c,i*Z,P[j]),Q2[i][j]=ksm(c,i,P[j]); fo(i,1,n){ C[i][0]=a[i]; fo(j,1,sum){ ci=a[i]%P[j]+(a[i]>=P[j])*P[j]; fd(k,j-1,1) ci=Q1[ci/Z][k]*Q2[ci%Z][k]%P[k]+(Q1[ci/Z][k]*Q2[ci%Z][k]>=P[k])*P[k]; C[i][j]=ksm(c,ci,mo);/**/C[i][j]%=mo; } } } int main(){ scanf("%d%d%lld%lld",&n,&m,&mo,&c); fo(i,1,n) read(a[i]); pre();make(1,n,1); while(m--){ read(cz),read(l),read(r); if(!cz){ change(1,n,1,l,r); continue; } ans=0; ask(1,n,1,l,r); if(!ans)printf("0\n");else write(ans); } }