题目链接: 戳我
落谷时间卡得真紧....test9 和 test11 根本过不去, 只有在 BZOJ 上面 A 掉了......
首先可以看得出这是一个线段树维护的数据结构题目吧 qwqwq
但是对于这种阶乘修改, 显然是不具备可加性的, 所以我们只能暴力修改.... 但是暴力修改时间复杂度是会炸天的!
但是我们再看一下 --
\(c^{a[i]^{a[i]^{...}}} \pmod p\)
我们想到了什么!!!-- 拓展欧拉定理啊 qwqwq
- \[a^b\equiv\begin{
- cases
- }a^{
- b\%\phi(p)
- }&{
- gcd(a,p)=1
- }\\a^b&{
- gcd(a,p)1,b\le\phi(p)
- }\\a^{
- b\%\phi(p)+\phi(p)
- }&gcd(a,p)\neq1,b\ge\phi(p)\end{
- cases
- }\pmod p\]
- (其实大家可以先去看看 [上帝与集合的正确用法] 这个题, 想必是有一些启发的)
根据拓展欧拉定理, 显然我们递归几次这个模数就会变成 1, 当模数变成 1 的时候, 显然就不需要再次计算了.
举个例子:
\[c^{a[i]^{a[i]}}=c^{a[i]^{a[i]\%\phi(\phi(p))+\phi(\phi(p))}+\phi(p)}\]
所以我们可以预先处理出来 p 的 phi 值都是多少, 结束条件为 phi 值 ==1.
代码如下:
- #include<iostream>
- #include<cstring>
- #include<cstdio>
- #include<algorithm>
- #include<cmath>
- #define MAXN 100010
- using namespace std;
- int n,m,c,p,cnt;
- int a[MAXN],phi[MAXN];
- struct Node{int l,r,tot,sum;}t[MAXN<<2];
- inline int Phi(int x)
- {
- long long cur_ans=x;
- int now=x;
- for(int i=2;i*i<=now;i++)
- {
- if(now%i==0) cur_ans=cur_ans/i*(i-1);
- while(now%i==0) now/=i;
- }
- if(now>1) cur_ans=cur_ans/now*(now-1);
- return cur_ans;
- }
- inline void init()
- {
- int cur=p;
- while(cur>1)
- {
- cur=Phi(cur);
- phi[++cnt]=cur;
- }
- //for(int i=1;i<=cnt;i++) printf("phi[%d]=%d\n",i,phi[i]);
- }
- inline long long fpow(long long x,long long y,long long mod)
- {
- long long cur_ans=1;
- int flag1=0,flag2=0;
- while(y)
- {
- if(y&1) cur_ans=cur_ans*x,flag1|=flag2;
- if(cur_ans>=mod) flag1=1,cur_ans%=mod;
- x=x*x;
- if(x>=mod) flag2=1,x%=mod;
- y>>=1;
- }
- if(flag1) cur_ans+=mod;
- return cur_ans;
- }
- inline long long solve(int l,int r,long long x,long long mod)
- {
- if(l==r) return x;
- return fpow(c,solve(l+1,r,x,phi[l+1]),mod);
- }
- inline int ls(int x){return x<<1;}
- inline int rs(int x){return x<<1|1;}
- inline void push_up(int x)
- {
- t[x].sum=(t[ls(x)].sum+t[rs(x)].sum)%p;
- t[x].tot=min(t[ls(x)].tot,t[rs(x)].tot);
- }
- inline void build(int x,int l,int r)
- {
- t[x].l=l,t[x].r=r;
- if(l==r){t[x].sum=a[l];return;}
- int mid=(l+r)>>1;
- build(ls(x),l,mid);
- build(rs(x),mid+1,r);
- push_up(x);
- }
- inline void update(int x,int ll,int rr)
- {
- if(t[x].tot>cnt) return;
- int l=t[x].l,r=t[x].r;
- if(l==r)
- {
- t[x].sum=solve(0,++t[x].tot,a[l],p)%p;
- return;
- }
- int mid=(l+r)>>1;
- if(ll<=mid) update(ls(x),ll,rr);
- if(mid<rr) update(rs(x),ll,rr);
- push_up(x);
- }
- inline long long query(int x,int ll,int rr)
- {
- int l=t[x].l,r=t[x].r;
- if(ll<=l&&r<=rr) return t[x].sum%p;
- int mid=(l+r)>>1;
- long long cur_ans=0;
- if(ll<=mid) cur_ans=(cur_ans+query(ls(x),ll,rr))%p;
- if(mid<rr) cur_ans=(cur_ans+query(rs(x),ll,rr))%p;
- return cur_ans;
- }
- int main()
- {
- #ifndef ONLINE_JUDGE
- freopen("ce.in","r",stdin);
- #endif
- scanf("%d%d%d%d",&n,&m,&p,&c);
- for(int i=1;i<=n;i++) scanf("%d",&a[i]);
- build(1,1,n);
- init();
- //for(int i=1;i<=cnt;i++) printf("%d\n",phi[i]);
- for(int i=1;i<=m;i++)
- {
- int op,l,r;
- scanf("%d%d%d",&op,&l,&r);
- if(op==0) update(1,l,r);
- else printf("%lld\n",query(1,l,r));
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2982949.html