模意义下除法若结果仍为整数的话，可以记录模数的所有质因子，计算这些质因子的次幂数，剩余的exgcd解决。
$O(n\log n)$但有9的常数（1e9内的数最多有9个不同的质因子），T了。
1 #include2 #include 3 #define rep(i,l,r) for (int i=(l); i<=(r); i++) 4 using namespace std; 5 6 const int N=100010; 7 int T,n,mod,op,w,tot,res,x,d[N][11],p[11],s[11]; 8 9 void frac(int n){10 for (int i=2; i*i<=n; i++) if (n%i==0){11 p[++tot]=i;12 while (n%i==0) n/=i;13 }14 if (n>1) p[++tot]=n;15 }16 17 void exgcd(int a,int b,int &x,int &y){18 if (!b) x=1,y=0;19 else exgcd(b,a%b,y,x),y-=a/b*x;20 }21 22 int main(){23 freopen("bzoj5334.in","r",stdin);24 freopen("bzoj5334.out","w",stdout);25 for (scanf("%d",&T); T--; ){26 scanf("%d%d",&n,&mod); tot=0; res=1; frac(mod);27 rep(i,1,10) s[i]=0;28 rep(i,1,n){29 scanf("%d",&op);30 if (op==1){31 scanf("%d",&w);32 rep(j,0,tot) d[i][j]=0;33 rep(j,1,tot)34 while (w%p[j]==0) w/=p[j],d[i][j]++,s[j]++;35 int x,y; res=1ll*res*w%mod;36 exgcd(w,mod,x,y); d[i][0]=(x%mod+mod)%mod;37 int ans=res;38 rep(j,1,tot) rep(k,1,s[j]) ans=1ll*ans*p[j]%mod;39 printf("%d\n",ans);40 }else{41 scanf("%d",&x); res=1ll*res*d[x][0]%mod;42 rep(j,1,tot) s[j]-=d[x][j];43 int ans=res;44 rep(j,1,tot) rep(k,1,s[j]) ans=1ll*ans*p[j]%mod;45 printf("%d\n",ans);46 }47 }48 }49 return 0;50 }
删除操作难以维护的话，考虑线段树分治即可。
1 #include2 #include 3 #define ls (x<<1) 4 #define rs (ls|1) 5 #define lson ls,L,mid 6 #define rson rs,mid+1,R 7 #define rep(i,l,r) for (int i=(l); i<=(r); i++) 8 using namespace std; 9 10 const int N=100010;11 int T,n,mod,x,op,tag[N<<2];12 struct P{ int l,r,v; }p[N];13 14 void push(int x){15 tag[ls]=1ll*tag[ls]*tag[x]%mod;16 tag[rs]=1ll*tag[rs]*tag[x]%mod;17 tag[x]=1;18 }19 20 void build(int x,int L,int R){21 tag[x]=1;22 if (L==R) return;23 int mid=(L+R)>>1;24 build(lson); build(rson);25 }26 27 void ins(int x,int L,int R,int l,int r,int k){28 if (L==l && r==R){ tag[x]=1ll*tag[x]*k%mod; return; }29 int mid=(L+R)>>1;30 if (r<=mid) ins(lson,l,r,k);31 else if (l>mid) ins(rson,l,r,k);32 else ins(lson,l,mid,k),ins(rson,mid+1,r,k);33 }34 35 int que(int x,int L,int R,int pos){36 if (L==R) return tag[x];37 int mid=(L+R)>>1; push(x);38 if (pos<=mid) return que(lson,pos); else return que(rson,pos);39 }40 41 int main(){42 for (scanf("%d",&T); T--; ){43 scanf("%d%d",&n,&mod);44 rep(i,1,n){45 scanf("%d",&op);46 if (op==1) scanf("%d",&x),p[i]=(P){i,n,x};47 else scanf("%d",&x),p[x].r=i-1,p[i].l=0;48 }49 build(1,1,n);50 rep(i,1,n) if (p[i].l) ins(1,1,n,p[i].l,p[i].r,p[i].v);51 rep(i,1,n) printf("%d\n",que(1,1,n,i));52 }53 return 0;54 }