NODSX2304A. 铲雪
给你一个序列，有 \(m\) 次操作，有两种。
- 给区间 \([l,r]\) 的每个数字平方；
- 询问区间 \([l,r]\) 每个数的倒数之和，对 \(998244353\) 取模。
暴力模拟时间复杂度是 \(O(n^2\log P)\) 的。
显然我们可以在一开始就对每个数取倒数，操作变成区间逐个平方和区间求和。暴力是 \((n^2)\) 的。
然后你自然地想用线段树去维护它。但是这个区间逐个平方十分难维护。
于是我们只能另辟蹊径。
每个数字只会进行平方操作，即变成 \(a_i^{2^k} \bmod P\)。根据扩展欧拉定理，若 \(a,p\) 互质，则 \(a^b \equiv a^{b\bmod \varphi(P)} (\bmod P)\)，变成求 \(a_i^{2^k \bmod 998244352} \bmod 998244353\)。
注意 \(2^k \bmod 998244352\) 不可以变成 \(2^{k \mod \varphi(998244352)} \bmod 998244352\)，因为 \(2,998244352\) 不互质。不过我们也没必要这么做，毕竟没什么用。
我们知道 \(998244352=119\times 2^{23}\)。求 \(2^k \bmod (119 \times 2^{23})\)。根据同余性质 \(ad \equiv bd(\bmod cd)\Rightarrow a\equiv b(\bmod c)(d>0)\)。有 \((2^{k-23} \bmod 119) \times 2^{23} = 2^k \bmod (119 \times 2^{23})(k\ge 23)\)。因此 \((2^{k-23} \bmod 119)\) 和 \(2^k \bmod (119 \times 2^{23})(k\ge 23)\) 形成双射。根据扩展欧拉定理，\(\varphi(119)=96\)，可以得到 \((2^{k-23} \bmod 119)\) 会形成较短的循环，循环节长度是 \(96\)。
实际上最短的循环节长度是 \(24\)。可以打表发现。这是因为 \(2^{24} \equiv 1 (\bmod 119)\)。
也就是说，每个数字在进行完 \(23\) 次操作后，每 \(24\) 次操作的值是一次循环。这个性质十分美丽。
考虑利用循环。意味着我们每次区间平方可以不用一个个数字改，可以预处理一次循环的每位的和，一共才 \(24\)。考虑在线段树上操作。记 \(s_{i,k}\) 表示节点 \(i\) 操作 \(k\) 次后的和。\(pushup\) 是好做的，只要 \(O(24)\)。每次修改找到若干段区间，然后把对应节点维护的值滚一轮，使 \(s_{i,k}\gets s_{i,k+1}\)。用时 \(O(24 \log n)\)。然后打个 \(tag\)，也是好维护的。
对于前面 \(23\) 次操作，我们暴力更新每个点在线段树上的值。因为每个点只会暴力 \(23\) 次，一共是 \(O(n 23 \log n)\) 的。具体实现参考了 dxw 的代码。在线段树区间修改的时候，如果存在点需要暴力更新，就把这个点拆出来暴力更新。拆这个点可能会裂开 \(O(\log n)\) 段区间，总共也是 \(O(23 n \log n)\) 的，复杂度正确。
总时间复杂度是 \(O((23+23+24)n \log n)\) 的。跑得还挺快，时限 \(2s\)，最慢点也才 \(0.5s\) 出头。
code
#include<bits/stdc++.h>
//#define LOCAL
#define sf scanf
#define pf printf
#define rep(x,y,z) for(int x=y;x<=z;x++)
#define per(x,y,z) for(int x=y;x>=z;x--)
using namespace std;
typedef long long ll;
const int N=1e5+7,mod=998244353;
ll ksm(ll a,ll b=mod-2) {
ll s=1;
while(b) {
if(b&1) s=s*a%mod;
a=a*a%mod;
b>>=1;
}
return s;
}
int n,m;
ll a[N];
int op,l,r;
inline ll _jia(int x,int y) {return x+y>=24?x+y-24:x+y;}
inline ll jia (ll x,ll y) {return x+y>=mod?x+y-mod:x+y;}
ll s[N<<2][30];
ll tag[N<<2];
int res[N<<2];
#define ls u<<1
#define rs u<<1|1
inline void maketag(int u,ll t) {
ll tmp[30];
memcpy(tmp,s[u],sizeof(ll)*24);
rep(i,0,23) s[u][i]=tmp[_jia(i,t)];
tag[u]=_jia(tag[u],t);
}
inline void pushdown(int u) {
if(tag[u]==0) return;
maketag(ls,tag[u]),maketag(rs,tag[u]);
tag[u]=0;
}
inline void pushup(int u) {
rep(i,0,23) s[u][i]=jia(s[ls][i],s[rs][i]);
res[u]=max(res[ls],res[rs]);
}
void build(int u,int l,int r) {
if(l==r) {
res[u]=23;
s[u][0]=a[l];
rep(i,1,23) {
s[u][i]=s[u][i-1]*s[u][i-1]%mod;
}
return;
}
int mid=(l+r)>>1;
build(ls,l,mid);build(rs,mid+1,r);
pushup(u);
}
void update(int u,int l,int r,int L,int R) {
if(l>=L&&r<=R&&!res[u]) {
maketag(u,1);
return;
}
if(l==r) {
--res[u];
rep(i,0,22) {
s[u][i]=s[u][i+1];
}
s[u][23]=s[u][22]*s[u][22]%mod;
return;
}
int mid=(l+r)>>1;
pushdown(u);
if(L<=mid) update(ls,l,mid,L,R);
if(mid+1<=R) update(rs,mid+1,r,L,R);
pushup(u);
}
ll query(int u,int l,int r,int L,int R) {
if(l>=L&&r<=R) {
return s[u][0];
}
int mid=(l+r)>>1;
pushdown(u);
ll as=0;
if(L<=mid) as=jia(as,query(ls,l,mid,L,R));
if(mid+1<=R) as=jia(as,query(rs,mid+1,r,L,R));
pushup(u);
return as;
}
int main() {
#ifdef LOCAL
freopen("in.txt","r",stdin);
freopen("my.out","w",stdout);
#endif
sf("%d%d",&n,&m);
rep(i,1,n) {
sf("%lld",&a[i]);
a[i]=ksm(a[i]);
}
build(1,1,n);
rep(i,1,m) {
sf("%d%d%d",&op,&l,&r);
if(op==0) {
update(1,1,n,l,r);
}else{
pf("%lld\n",(query(1,1,n,l,r)));
}
}
}