洛谷P3747 [六省联考 2017] 相逢是问候题解

题目链接：洛谷P3747 [六省联考 2017] 相逢是问候

题意：B 君希望以维护一个长度为 \(n\) 的数组，这个数组的下标为从 \(1\) 到 \(n\) 的正整数。

一共有 \(m\) 个操作，可以分为两种：

0 l r 表示将第 \(l\) 个到第 \(r\) 个数（ \(a_l,a_{l+1} ...a_r\)）中的每一个数 \(a_i\) 替换为 \(c^{a_i}\) ，即 \(c\) 的 \(a_i\) 次方，其中 \(c\) 是输入的一个常数，也就是执行赋值 \(a_i = c^{a_i}\)。

1 l r 求第 \(l\) 个到第 \(r\) 个数的和，也就是输出： \(\sum_{i=l}^{r}a_i\)

因为这个结果可能会很大，所以你只需要输出结果 \(\bmod \ p\) 的值即可。

建议先去做一做 P4139 和 P4145 ，这道题就是这俩的综合加强版本题解在这里 link1 link2

有个结论

\[ O(\varphi^* (p)=1)=O(\log p) \]

注：这里左边指的是最小的一个正整数 \(x\) 使得 \[ \begin{aligned} \begin{matrix} &\underbrace{\varphi(\varphi(\dots\varphi(p)))}=1 \\ &x\, \text{个}\,\varphi\quad\,\,\,\, \end{matrix} \end{aligned} \] 这里不再证明，见上面的link1

不难发现，对于某个数至多修改 \(O(\log p)\) 次就会变成一个常数

考虑直接在线段树上暴力更新信息

更新的时候不要直接用快速幂，这样会多一个 \(O(\log p)\)

考虑预处理 \(c^i\) 和 \(c^{ik}\) ，然后就可以 \(O(1)\) 查询了（这个就是光速幂的原理）

\(k\) 一般取到 \(\sqrt{p}\) ，这里我取了32768，即 \(2^{15}\)

然后 \(p\) 是不变的，所以可以预处理一下 \(\varphi^i(p)\)

其他的，详见代码

时间复杂度是 \(O(n \log n \log p)\) 的

证明：（势能分析） \[ O\left(2\sqrt{p}+\sqrt{p}{\log p}+n \times \dfrac{n \log p}{n} \times \log n\right) = O(n \log n \log p) \] 代码如下，~~写的很烂~~ qwq

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
namespace FastIO
{
    #define gc() readchar()
    #define pc(a) putchar(a)
    #define SIZ (int)(1e6+15)
    char buf1[SIZ],*p1,*p2;
    char readchar()
    {
        if(p1==p2)p1=buf1,p2=buf1+fread(buf1,1,SIZ,stdin);
        return p1==p2?EOF:*p1++;
    }
    template<typename T>void read(T &k)
    {
        char ch=gc();T x=0,f=1;
        while(!isdigit(ch)){if(ch=='-')f=-1;ch=gc();}
        while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=gc();}
        k=x*f;
    }
    template<typename T>void write(T k)
    {
        if(k<0){k=-k;pc('-');}
        static T stk[66];T top=0;
        do{stk[top++]=k%10,k/=10;}while(k);
        while(top){pc(stk[--top]+'0');}
    }
}using namespace FastIO;
#define N (int)(5e4+15)
#define P ((1<<15)-1)
int n,p[30],cnt,c,mod;
int a[N][30],sum[N<<2],mn[N<<2];
int pw1[30][P+15],pw2[30][P+15];
#define ls(at) (at<<1)
#define rs(at) (at<<1|1)
int phi(int n)
{
    int ans=n;
    for(int i=2; i<=n/i; i++)
        if(n%i==0)
        {
            ans=ans/i*(i-1);
            while(n%i==0)n/=i;
        }
    if(n>1)ans=ans/n*(n-1);
    return ans;
}
int Mod(int x,int p){return x>=p?x%p+p:x;}
void init()
{
    for(int i=0; i<=cnt; i++)
    {
        pw1[i][0]=pw2[i][0]=1;
        for(int j=1; j<1<<15; j++)
            pw1[i][j]=Mod(pw1[i][j-1]*c,p[i]);
        pw2[i][1]=Mod(pw1[i][P]*c,p[i]);
        for(int j=2; j<1<<15; j++)
            pw2[i][j]=Mod(pw2[i][j-1]*pw2[i][1],p[i]);
    }
}
int Pow(int n,int i)
{
    return Mod(pw1[i][n&P]*pw2[i][n>>15],p[i]);
}
int calc(int x,int dep,int i)
{
    if(!dep)return Mod(x,p[i]);
    if(i==cnt)return 1;
    return Pow(calc(x,dep-1,i+1),i);
}
void push_up(int at)
{
    mn[at]=min(mn[ls(at)],mn[rs(at)]);
    sum[at]=sum[ls(at)]+sum[rs(at)];
    if(sum[at]>=p[0])sum[at]%=p[0];
}
void build(int l,int r,int at)
{
    mn[at]=0;
    if(l==r){sum[at]=a[l][0];return;}
    int mid=(l+r)>>1;
    build(l,mid,ls(at));
    build(mid+1,r,rs(at));
    push_up(at);
}
void update(int nl,int nr,int l,int r,int at)
{
    if(mn[at]>cnt)return;
    if(l==r)
    {
        ++mn[at];
        sum[at]=a[l][mn[at]];
        return;
    }
    int mid=(l+r)>>1;
    if(nl<=mid)update(nl,nr,l,mid,ls(at));
    if(nr>mid)update(nl,nr,mid+1,r,rs(at));
    push_up(at);
}
int query(int nl,int nr,int l,int r,int at)
{
    if(nl<=l&&r<=nr)return sum[at];
    if(nl>r||nr<l)return 0;
    int mid=(l+r)>>1;
    int res=query(nl,nr,l,mid,ls(at))+query(nl,nr,mid+1,r,rs(at));
    return res%p[0];
}
signed main()
{
    // ios::sync_with_stdio(0);
    // cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int Q,op,l,r;
    read(n);read(Q);read(p[0]);read(c);
    cnt=0;
    while(p[cnt]>1)++cnt,p[cnt]=phi(p[cnt-1]);
    init();
    for(int i=1; i<=n; i++)
    {
        read(a[i][0]);
        for(int j=1; j<=cnt+1; j++)
            a[i][j]=calc(a[i][0],j,0)%p[0];
        a[i][0]%=p[0];
    }
    // for(int i=1; i<=n; i++)
    //     for(int j=0; j<=cnt+1; j++)
    //         cout << a[i][j] << " \n"[j==cnt+1];
    build(1,n,1);
    while(Q--)
    {
        read(op);read(l);read(r);
        if(op==0)update(l,r,1,n,1);
        else write(query(l,r,1,n,1)),pc('\n');
    }
    return 0;
}