当前位置: 首页 > news >正文

题解: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;
}
http://www.hskmm.com/?act=detail&tid=18257

相关文章:

  • 当不小心误触了一个事件该如何删除呢
  • 烧录工具使用方法大公开:实用说明文档奉上
  • 警惕新型XCSSET macOS恶意软件变种,专攻Xcode开发者
  • 前端面经-高级开发(华为od) - 实践
  • 2025权威排行榜:公众号编辑器Top 6深度测评,哪款最适合你
  • 个人简介
  • 【图床】存几张图
  • 完整教程:Sass:CSS 预处理器
  • DDL表操作
  • 第二周第五天2.5
  • yolo
  • 什么是 glTF:完整指南
  • 垃圾收集器与核心算法详解(上)
  • 在Debian系统上修改开源软件源代码制作patch - 教程
  • WSL2搭建wordpress遇到的一点问题
  • 需求的系统规划 3
  • 430亿美元押注英国,Salesforce 加码 AI 投资
  • C# 中 ref 和 out 的学习笔记
  • C# 序列化三种方式
  • 区别:Modbus RTU 和 Modbus TCP
  • 记录安装机器/深度学习环境(conda、CUDA、pytorch)时的一些问题
  • 详细介绍:大数据毕业设计选题推荐:基于Hadoop+Spark的全球能源消耗数据分析与可视化系统
  • 深入解析:自动化接口框架搭建分享-pytest
  • 手撕深度学习之CUDA并行规约算法(上篇):硬核揭秘200%性能提升的GPU优化之道,从硬件特性到算法实现的完整进阶指南
  • 实战需求分析
  • 【RabbitMQ】主题(Topics)与主题交换机(Topic Exchange)
  • Ubuntu上编译 Linux_RT 内核
  • vue3 + vite Cannot access ‘xxx‘ before initialization
  • 《“悬荡”于理想与现实之间:一份关于人机共生未来的思想实验评估》
  • 区别:RS-232、RS-422、RS-485