DS 笔记：奈芙莲树学习笔记（Ynoi）

Aw顿顿 · 2021-08-17 09:39:39 · 题解

人生中第一道 Ynoi，本来是 900 粉 Flag 但是不小心就做出来了，那就提前庆祝 900 粉吧（虽然发这份题解的时候还没到）。

其实此题从任何一个角度来说都不难的。

P3934 [Ynoi2016] 炸脖龙 I

给定一个长度为 n 的区间 a，进行 m 次操作：

将区间 [l,r] 加上 x。

求 a(l)^{a(l+1)^{\cdots^{a(r)}}}\bmod p。

如果我们记 f(x,x)=a_x 且 f(x,y)=a^{f(x+1,j)}，那么我们就可以用递归的形式表示操作二：求 f(l,r)。由于该操作并不具有可加性，考虑用奈芙莲树解决（好像是神蛙起的名字），实际上这个数据结构就是差分树状数组与扩展欧拉定理的有机结合。

前置知识

上一次看到次幂的次幂的次幂……还是在上帝与集合的正确用法那题，而这道题目又套上了区间操作，于是考虑前置知识：

欧拉函数求值
扩展欧拉定理
树状数组基础

虽然这两个扩展资料对于此题来说是不够的，但是我们在接下来的讲解之中会简单介绍具体操作，因此不必担心。另外，本文的数学公式均在模 p 意义下讨论。

操作方法

通过扩展欧拉定理，f(l,r) 可以转化为 a_l^{t}，其中：

t=\begin{cases}f(l+1,r)\bmod p+\varphi(p)&f(l+1,r)\ge\varphi(p)\\f(l+r,r)\bmod p\end{cases}

由因数分解可得，这样的迭代最多进行 \log 次，这里给出简要证明。由 \varphi 的定义可以得到：

\varphi(n)=n\prod\limits_{i=1}^{n}\left(1-\dfrac{1}{p_i}\right)

若 n 是偶数则乘式中一定存在一项 1-\frac{1}{2}，反之则一定存在一个形如 \frac{a}{b} 的因式满足 a\equiv 2\pmod 2，可以归纳到偶数里。因此最多进行 \log 次递归就可以得到答案。接下来考虑分类化简情况：

如果在这一区间内存在任意一个 a_i=1，那么在 i 之后的所有次幂都可以忽略，因为底数为 1。
如果不存在 1，且区间长度大于 5，那么简单计算：

f(l,l+5)\ge 2^{2^{2^{2^2}}}\ge 2\times 10^7

所以在扩展欧拉定理中，这样的大小已经超过了 p，因此不需要再进一步分类讨论。因此对于第二位到第六位的情况（第一位是底数不在乎，因此是第二位到第六位），可以暴力计算，而再之后的情况可以直接扔到递归式子里面算即可，可以用树状数组维护。

具体实现

首先预处理出 \varphi 值。

inline void getphi(){
    int cnt=0;phi[1]=1;
    for(int i=2;i<M;i++){
        if(!vis[i])pr[++cnt]=i,phi[i]=i-1;
        for(int j=1;j<=cnt&&pr[j]*i<M;j++){
            vis[pr[j]*i]=1;
            if(i%pr[j])phi[pr[j]*i]=phi[i]*(pr[j]-1);
            else phi[pr[j]*i]=phi[i]*pr[j];
            if(i%pr[j]==0)break;
        }
    }
}

具体实现上不难。对于操作一，我们只需要用差分树状数组进行两次区间加即可：

inline void add(int x,long long y){
    id++;
    while(x<=n){
        t[x]+=y;
        x+=lowbit(x);
    }
}inline void work1(int l,int r,int c){
  add(l,c);
  add(r+1,-c);
}//区间修改

而操作二首先进行特判，然后就可以分类讨论了。对于前五位进行暴力，后面的用扩展欧拉定理计算。具体操作步骤如：

特殊情况特殊处理。
取二到六位进行处理，找出最前面的 a_i=1 并 r\gets i。
累乘判断是否需要递归，如需递归则规模变小。
否则暴力计算。

inline int work2(int l,int r,int mod){//区间次幂查询
    if(a[l]%mod==0)return 0;
    else if(mod==1)return 1;
    else if(l==r){
        if(a[l]>=mod)return a[l]%mod+mod;
        else return a[l]%mod;
    }int len=min(l+5,r);
    for(int i=l+1;i<=len;i++)
        if(a[i]==1){
            len=i;
            break;
        }
    int g=0,last=a[len];
    for(int i=len-1;i>=l+1;i--){
        g=last,last=1;
        while(g--){
            last=last*a[i];
            if(last>phi[mod])
                return ksm(a[l],work2(l+1,r,phi[mod])+phi[mod],mod);
        }
    }return ksm(a[l],last,mod);
}

全文代码实现

本身由于是否开 \texttt{long long} 的问题被弄得很晕，因此代码加了 #define int long long 因此可读性可能不是很好，但是在这道题这样写是没有问题的。这里提出几个注意点：

快速幂一律底数取模。
结构体中重定义 [] 并记录修改次数以优化常数。
预处理条件写 <MAXM 而非 <=MAXM 否则会越界。
用快写输出后记得换行。

#include<bits/stdc++.h>
#define int long long
#define N 500005
#define M 20000005
using namespace std;
inline int read(){
   register int s=0,w=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9')s=s*10+ch-'0',ch=getchar();
   return s*w;
}inline void print(int x){
    if(x<0){putchar('-');x=-x;}
    if(x>9)print(x/10);
    putchar(x%10+'0');
}inline int lowbit(int x){return x&(-x);}
int q,n,phi[M],pr[M>>3],id;
int t[N];char vis[M];
inline int query(int x){
    int s=0;//区间查询  
    while(x){
        s+=t[x];
        x-=lowbit(x);
    }return s;
}struct node{//重载 [] 运算符
    int v[N],l[N];
    inline int&operator[](int x){
        if(l[x]!=id)l[x]=id,v[x]=query(x);
        return v[x];
    }
}a;
inline void add(int x,int c){
    id++;//区间修改 记录修改次数  
    while(x<=n){
        t[x]+=c;
        x+=lowbit(x);
    }
}inline int ksm(int b,int p,int mod){
    int s=1;b%=mod;//底数先取模
    while(p){
        if(p&1)s=1ll*s*b%mod;
        b=b*b%mod;p>>=1;
    }return s;
}inline void getphi(){//预处理 phi
    int cnt=0;phi[1]=1;
    for(int i=2;i<M;i++){
        if(!vis[i])pr[++cnt]=i,phi[i]=i-1;
        for(int j=1;j<=cnt&&pr[j]*i<M;j++){
            vis[pr[j]*i]=1;
            if(i%pr[j])phi[pr[j]*i]=phi[i]*(pr[j]-1);
            else phi[pr[j]*i]=phi[i]*pr[j];
            if(i%pr[j]==0)break;
        }
    }
}inline void work1(int l,int r,int c){add(l,c);add(r+1,-c);}
inline int work2(int l,int r,int mod){
    if(a[l]%mod==0)return 0;
    else if(mod==1)return 1;
    else if(l==r){
        if(a[l]>=mod)return a[l]%mod+mod;
        else return a[l]%mod;
    }int len=min(l+5,r);
    for(int i=l+1;i<=len;i++)
        if(a[i]==1){//找 1
            len=i;
            break;
        }
    int g=0,last=a[len];
    for(int i=len-1;i>=l+1;i--){
        g=last,last=1;
        while(g--){
            last=last*a[i];
            if(last>phi[mod])
                return ksm(a[l],work2(l+1,r,phi[mod])+phi[mod],mod);
        }
    }return ksm(a[l],last,mod);
}signed main(){
    n=read();q=read();getphi();
    for(int i=1;i<=n;i++){
        scanf("%lld",&a[i]);
        add(i,a[i]-a[i-1]);//做差分 
    }for(int i=1;i<=q;i++){
        int op,l,r,c;
        op=read();l=read();r=read();c=read();
        if(op==1)work1(l,r,c);
        else print(work2(l,r,c)%c),putchar('\n');
    }return 0;
}