题解：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\)，我们可以简单分讨一下：

• 若 \(a_i\le1\)，跳过；

• 若 \(cnt_i=0\)，\(a_i\leftarrow \lfloor\sqrt{a_i}\rfloor\)；

• 若 \(cnt_i\ge1\)，\(cnt_i \leftarrow cnt_i-1\)。

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

• 若第 \(i\) 块全为 \(1\)，跳过；

• 若 \(mn_i=0\)，直接把第 \(i\) 块当作散块处理（由势能分析，这一步的复杂度是有保障的）；

• 否则，将第 \(i\) 块上的所有 \(cnt_j\leftarrow cnt_j-1\)。

但接下来，我们还有一个问题没有解决——查询时，作为 \(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;
}