题解：P7334 [JRKSJ R1] 吊打

· · 题解

本 DS 领域萌新花了 4h 才切掉此题，遂写篇题解纪念一下。

分析

首先需要明确一点：这题不能直接维护原序列，因为平方时不能直接取模，这就导致结果会非常大，很容易溢出。

为什么不能直接取模呢？举个例子，对 10^8 平方一次再开根，答案还是 10^8；但如果平方时对 998244353 取模了，答案就会变成 346563789，这显然不对。

那么考虑不直接维护原序列该怎么做。暂时不管开根，只考虑平方。设 a_i 被平方了 cnt_i 次，那么可以发现，a_i 会变为 a_i^{2^{cnt_i}}。此时 2^{cnt_i} 同样因为太大，也无法维护；但是 cnt_i 就小得多了，至多为 2\times10^5。因此，我们可以维护 cnt_i，将区间平方转化为区间加。这个可以搞上一个分块。

于是来考虑有开根该怎么做。还是本着维护 cnt_i 的思想，对于散块中的任意位置 i，我们可以简单分讨一下：

然后考虑对于整块该怎么处理。我们设 mn_i 表示第 i 块上的 cnt 的最小值，当前整块的编号为 i，依然分讨：

但接下来，我们还有一个问题没有解决——查询时，作为 a_i 次数的 2^{cnt_i} 依然很大，没法直接求，怎么办？

这时候就需要一点——数学技巧！

我们希望找到一种手段，可以把 a_i 的次数降下来，也就是通常所说的降幂。

降幂？有没有觉得很熟悉——没错，扩展欧拉定理！

由扩展欧拉定理，我们知道，当 a\perp m 时，有 a^b \equiv a^{b \mod \varphi(m)}\pmod m。

而此题中，m=998244353，是一个质数，所以 \varphi(m)=m-1=998244352。也就是说，运用扩展欧拉定理降幂之后，a_i 的次数变为 2^{cnt_i} \mod 998244352，这个数就可以用快速幂直接求了！

于是我们就可以愉快地 AC 了！

代码

代码中的变量名与上面使用的名称保持一致，（应该）很好看懂。

#include<iostream>
#include<cmath>
#define ll unsigned long long
using namespace std;

const int N=2e5+5;
const int M=1e3+5;
const ll p=998244353;

int n,m;
ll ans;

int a[N];

namespace OIfast{

    char buf[1<<21],*p1,*p2,*top, buffer[1<<21];
    #define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?0:*p1++)
    #define gc getchar()

    inline int read(){
        int n=0;char c=gc;
        while(!isdigit(c))c=gc;
        while(isdigit(c))n=(n<<3)+(n<<1)+(c^48),c=gc;
        return n;
    }

}using namespace OIfast;

inline ll qpow(ll a,int b,ll mod){
    ll res=1;
    while(b){
        if(b&1)(res*=a)%=mod;
        b>>=1,(a*=a)%=mod;
    }
    return res;
}

namespace FK{

    int k/*块长*/,tot/*块数*/;

    int cnt[N]/*平方次数*/;

    int L[M]/*L[i] -> 第 i 块的左端点*/,R[M]/*R[i] -> 第 i 块的右端点*/,loc[N]/*loc[i] -> 第 i 个数在第几块*/,mn[M]/*cnt*/,la[M]/*cnt*/;
    bool flag[M]/*是否全为 1*/;

    inline void pushup(int i){
        mn[i]=1e9,flag[i]=1;for(int j=L[i];j<=R[i];++j)mn[i]=min(mn[i],cnt[j]),flag[i]&=(a[j]<=1);
        return ;
    }

    inline void pushdown(int i){
        for(int j=L[i];j<=R[i];++j)cnt[j]+=la[i];
        return la[i]=0,void();
    }

    inline void init(){
        k=sqrt(n),tot=ceil((1.0*n)/(1.0*k));
        for(int i=1;i<=tot;++i){
            L[i]=(i-1)*k+1,R[i]=min(n,L[i]+k-1);
            for(int j=L[i];j<=R[i];++j)loc[j]=i;
            pushup(i);
        }
        return ;
    }

    inline void sk(int l,int r){
        pushdown(loc[l]);
        for(int i=l;i<=r;++i){
            if(a[i]<=1)continue ;
            if(!cnt[i])a[i]=sqrt(a[i]);
            else --cnt[i];
        }
        return pushup(loc[l]),void();
    }

    inline void upd1(int l,int r){//开根
        if(loc[l]==loc[r])sk(l,r);
        else{
            sk(l,R[loc[l]]),sk(L[loc[r]],r);
            for(int i=loc[l]+1;i<=loc[r]-1;++i){
                if(flag[i])continue ;
                if(mn[i]+la[i]<=1)sk(L[i],R[i]);
                else --la[i],--mn[i];
            }
        }
        return ;
    }

    inline void upd2(int l,int r){//平方
        if(loc[l]==loc[r]){
            pushdown(loc[l]);for(int i=l;i<=r;++i)++cnt[i];pushup(loc[l]);
        }else{
            pushdown(loc[l]);for(int i=l;i<=R[loc[l]];++i)++cnt[i];pushup(loc[l]);
            pushdown(loc[r]);for(int i=L[loc[r]];i<=r;++i)++cnt[i];pushup(loc[r]);
            for(int i=loc[l]+1;i<=loc[r]-1;++i)++la[i],++mn[i];
        }
        return ;
    }

}using namespace FK;

inline void work(){
    int op=read(),l=read(),r=read();
    return op==1?upd1(l,r):upd2(l,r),void();
}

signed main(){
    n=read(),m=read();for(int i=1;i<=n;++i)a[i]=read();
    init();while(m--)work();
    for(int i=1;i<=tot;++i)pushdown(i);
    for(int i=1;i<=n;++i)(ans+=qpow(a[i],qpow(2,cnt[i],p-1),p))%=p;
    return printf("%lld\n",ans),0;
}