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

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

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

• 0 l r 表示将第 l l l 个到第 r r r 个数（ a l , a l + 1 . . . a r a_l,a_{l+1} ...a_r al​,al+1​...ar​）中的每一个数 a i a_i ai​ 替换为 c a i c^{a_i} cai​ ，即 c c c 的 a i a_i ai​ 次方，其中 c c c 是输入的一个常数，也就是执行赋值 a i = c a i a_i = c^{a_i} ai​=cai​。
• 1 l r 求第 l l l 个到第 r r r 个数的和，也就是输出： ∑ i = l r a i sum_{i=l}^{r}a_i ∑i=lr​ai​

因为这个结果可能会很大，所以你只需要输出结果   m o d     p bmod p mod p 的值即可。

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

有个结论

O ( φ ∗ ( p ) = 1 ) = O ( log ⁡ p ) O(varphi^* (p)=1)=O(log p) O(φ∗(p)=1)=O(logp)

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

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

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

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

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

k k k 一般取到 p sqrt{p} p ​ ，这里我取了32768，即 2 15 2^{15} 215

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

其他的，详见代码

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

证明：（势能分析）
O ( 2 p + p log ⁡ p + n × n log ⁡ p n × log ⁡ n ) = O ( n log ⁡ n log ⁡ p ) Oleft(2sqrt{p}+sqrt{p}{log p}+n times dfrac{n log p}{n} times log nright) = O(n log n log p) O(2p ​+p ​logp+n×nnlogp​×logn)=O(nlognlogp)
代码如下，写的很烂 qwq

#include 
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++;
    }
    templatevoid 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;
    }
    templatevoid 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>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;
}

哇。想了一天的毒瘤题。脑袋要裂开了 -> q779太菜了

嗯。本题的综合性非常强。

不就是个 线段树+势能分析+扩展欧拉定理+光速幂 吗（逃

参考文献

[1] https://www.luogu.com.cn/blog/s-r-f/solution-p3747

转载请说明出处