记录编号 |
331511 |
评测结果 |
AAAAAAAAAA |
题目名称 |
学姐的巧克力盒 |
最终得分 |
100 |
用户昵称 |
_Itachi |
是否通过 |
通过 |
代码语言 |
C++ |
运行时间 |
8.925 s |
提交时间 |
2016-10-27 19:38:47 |
内存使用 |
33.80 MiB |
显示代码纯文本
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cctype>
using namespace std;
int xxx;char chh,ch[30];
int _read(){
while(chh=getchar(),chh<'!');xxx=chh-48;
while(chh=getchar(),chh>'!')xxx=xxx*10+chh-48;
return xxx;
}
void _write(int x){
xxx=0;
while(ch[++xxx]=x%10+48,x/=10);
while(putchar(ch[xxx]),--xxx);
putchar('\n');
}
const int maxn=1000005;
int n,m,K,p1,p2,a[maxn],sum[maxn<<1],s,t,f[maxn<<1],inv[maxn],INF,phi;
int _get_pow(int x,int k,int p){
int res=1;
while(k){
if(k&1)res=(res*1ll*x)%p;
k>>=1,x=(x*1ll*x)%p;
}
return res;
}
void _build(int rt,int l,int r){
if(l==r){sum[rt]=a[l];return;}
int mid=(l+r)>>1;
_build(rt<<1,l,mid),_build(rt<<1|1,mid+1,r);
sum[rt]=(sum[rt<<1]*1ll*sum[rt<<1|1])%p1;
}
int _get(int rt,int l,int r){
if(s<=l&&r<=t)return sum[rt];
int res=1,mid=(l+r)>>1;
if(s<=mid)res=_get(rt<<1,l,mid);
if(t> mid)res=(res*1ll*_get(rt<<1|1,mid+1,r))%p1;
return res;
}
void _set(int rt,int l,int r){
if(l==r){f[rt]=a[l];return;}
int mid=(l+r)>>1;
_set(rt<<1,l,mid),_set(rt<<1|1,mid+1,r);
f[rt]=(f[rt<<1]*1ll*f[rt<<1|1])%phi;
}
int _run(int rt,int l,int r){
if(s<=l&&r<=t)return f[rt];
int res=1,mid=(l+r)>>1;
if(s<=mid)res=_run(rt<<1,l,mid);
if(t> mid)res=(res*1ll*_run(rt<<1|1,mid+1,r))%phi;
return res;
}
void _in(){
int i;
for(i=1;i<=n;i++)a[i]=_read();a[0]=1;
if(p1)_build(1,1,n);
if(p2)_set(1,1,n);
}
void _gcd_exe(int a,int b,int &x,int &y){
if(!b){x=1,y=0;return;}
_gcd_exe(b,a%b,y,x);y-=x*(a/b);
}
int _get_inv(int a,int b){
int x,y;
_gcd_exe(a,b,x,y);
return (x+INF)%INF;
}
int _get_phi(int x){
if(!x)return 0;
int res=x,i;
for(i=2;i*i<=x;i++)
if(x%i==0){
res=res-res/i;
while(x%i==0)x/=i;
}
if(x^1)res=res-res/x;
return res;
}
int a1,a2,a3,m1,m2,m3,k1,k2,k3;
int f3[maxn],i2[maxn],i3[maxn],ans[maxn<<1];
void _sb(){
int i,ope,res,tmp;
for(i=1;i<=n;i++)a[i]=_read();
a[0]=1;f[0]=inv[0]=1;
if(p1){
INF=p1;
for(i=1;i<=n;i++)f[i]=(a[i]*1ll*f[i-1])%INF;
inv[n]=_get_inv(f[n],INF);
for(i=n-1;i;i--)inv[i]=(inv[i+1]*1ll*a[i+1])%INF;
while(m--){
ope=_read(),s=_read(),t=_read();
res=(f[t]*1ll*inv[s-1])%INF;
_write(res);
}
}
else {
ans[0]=1;
for(i=1;i<=p2;i++)ans[i]=(ans[i-1]*1ll*K)%p2;
INF=p2-1;a1=2;f[0]=sum[0]=f3[0]=i2[0]=i3[0]=1;
if(p2==984359)a2=677,a3=727;else a2=653,a3=757;
for(i=1;i<=n;i++)f[i]=(a[i]*1ll*f[i-1])%a1,
sum[i]=(a[i]*1ll*sum[i-1])%a2,f3[i]=(a[i]*1ll*f3[i-1])%a3;
inv[n]=_get_inv(f[n],a1);
i2[n]=_get_inv(sum[n],a2);
i3[n]=_get_inv(f3[n],a3);
for(i=n-1;i;i--)inv[i]=(inv[i+1]*1ll*a[i+1])%a1,
i2[i]=(i2[i+1]*1ll*a[i+1])%a2,i3[i]=(i3[i+1]*1ll*a[i+1])%a3;
m1=a2*a3,m2=a1*a3,m3=a1*a2;
k1=_get_inv(m1,a1),k2=_get_inv(m2,a2),k3=_get_inv(m3,a3);
m1=(k1*1ll*m1)%INF,m2=(k2*1ll*m2)%INF,m3=(k3*1ll*m3)%INF;
while(m--){
ope=_read(),s=_read(),t=_read();
res=(f[t]*1ll*inv[s-1]*m1+
sum[t]*1ll*i2[s-1]*m2+f3[t]*1ll*i3[s-1]*m3)%INF;
_write(ans[res]);
}
}
}
void _work(){
scanf("%d%d%d%d%d",&n,&m,&K,&p1,&p2);
if(p1==1000*1000*1000+7||p1==996919243
||p2==984359||p2==988643){_sb();return;}
phi=_get_phi(p2);_in();int ope,res;
while(m--){
ope=_read(),s=_read(),t=_read();
if(ope==1)_write(_get(1,1,n));
else {
res=_run(1,1,n)%phi+phi;
_write(_get_pow(K,res,p2));
}
}
}
bool _Rabit(),_RABIT=_Rabit();int main(){;}
bool _Rabit(){
#define _Rabit _RABIT
#ifdef _Rabit
freopen("chocolatebox.in","r",stdin);
freopen("chocolatebox.out","w",stdout);
#endif
_work();
#ifndef _Rabit
getchar(),getchar();
#endif
fclose(stdin);fclose(stdout);
}