自动搬运

查看原文

来自洛谷，原作者为

	DaiRuiChen007 白鸟白鸟 不要回头望 你要替我飞去那地方 一去那地方 那是你我共同故乡

搬运于2025-08-24 23:15:56，当前版本为作者最后更新于2025-06-09 23:07:58，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

Problem Link

题目大意

给定长度为 $n$ 的环，在第 $i$ 个点有 $1-p_i$ 的概率停止，否则走到 $(i+d)\bmod n$。

初始给定 $p'_0\sim p'_{m-1}$，$p_i=p'_{i\bmod m}$，然后给出一棵树，$q$ 个叶子，每个叶子表示对 $p$ 的单点修改（修改的位置不同）。

对每个节点，求出进行其子树内所有叶子代表的修改后，随机从一个点出发后期望走多少步停止（开始算一步）。

数据范围：$n\le 10^{16},m\le 5000,q\le 10^5$，$\gcd(n,d)=1$。

思路分析

从 $d=1$ 开始，写成 dp 的形式就是 $f_i=1+p_if_{i+1}$，然后在长度为 $n$ 的环上 dp。

那么解 $f$ 只要设 $f_0=x$，然后带入一次函数复合一圈即可。

如果 $n$ 很小，直接建线段树，区间 $[l,r]$，把 $f_l,\sum f_i$ 表示成关于 $f_{r+1}$ 的一次函数，合并很简单。

那么 $n$ 很大的时候，先对 $p'_0\sim p'_{m-1}$ 建线段树，然后类似倍增的方式拷贝 $\dfrac nm$ 份，修改的时候类似主席树，把一条链复制一遍。

然后维护子树内所有操作，启发式合并比较简单，但更优的做法是线段树合并，即两棵子树中有一棵被修改过，另一棵则是原树上节点，就返回修改过的一棵，复杂度不变。

这样就在 $\mathcal O(q\log n)$ 的复杂度内完成了修改。

然后回到原问题，把 $p_i$ 变成 $p_{id\bmod n}$ 然后又回到 $d=1$ 的情况，那么对 $q=0$ 的情况建出类线段树结构，然后仿照上面的过程维护即可。

先考虑 $q=0$ 时如何单纯维护答案。

那么我们可以看成 $\prod_{i=0}^{n-1} F((id\bmod n)\bmod m)$，其中 $F(i)$ 是 $p'_i$ 对应信息。

两个取模太困难了，写成 $\prod_{i=0}^{n-1}F((id-\lfloor id/n\rfloor n)\bmod m)$，包含取整和求和可以想到万能欧几里得。

考察直线 $y=\left\lfloor\dfrac{xd}n\right\rfloor$，维护 $u=0$，每经过一条横线 $u\gets u-n$，每经过一条竖线 $s\gets s\times F(u),u\gets u+d$。

那么维护初始 $u\in [0,m)$ 时的答案，以及最终 $u$ 的偏移量就能解决。

然后考虑如何建立线段树结构。

注意到万欧过程中维护 $u\in[0,m)$ 的答案是每次合并两个信息得到的，那么每个维护的答案可以看成 $F$ 的一个区间积，因此不维护答案，而是把合并的过程建树，每个值对应一个树上节点。

由于万欧只有 $\mathcal O(\log n)$ 次合并，因此初始节点个数 $\mathcal O(m\log n)$，最大深度 $\mathcal O(\log n)$，直接看成类线段树结构进行刚才的过程即可。

时间复杂度 $\mathcal O((m+q)\log n)$。

代码呈现

#include<bits/stdc++.h>
#define ll long long
#define LL __int128
using namespace std;
const int MAXN=1e5+5,MOD=998244353,MAXS=2e7+5;
ll ksm(ll a,ll b=MOD-2) { ll s=1; for(;b;a=a*a%MOD,b>>=1) if(b&1) s=s*a%MOD; return s; }
struct func {
	ll a,b,c,d; //f=ax+b, s=cx+d
	inline friend func operator +(const func &l,const func &r) {
		return {l.a*r.a%MOD,(l.b+l.a*r.b)%MOD,(l.c*r.a+r.c)%MOD,(l.d+r.d+l.c*r.b)%MOD};
	}
	ll val() { return (b*ksm(1+MOD-a)%MOD*c+d)%MOD; }
};
func f[MAXS];
ll n,d,siz[MAXS];
int m,q1,q2,ls[MAXS],rs[MAXS],tot;
int comb(int x,int y) {
	if(!x||!y) return x|y;
	++tot,ls[tot]=x,rs[tot]=y;
	siz[tot]=siz[x]+siz[y],f[tot]=f[x]+f[y];
	return tot;
}
struct info {
	int d,f[5005];
	info() { d=0,memset(f,0,sizeof(f)); }
	inline friend info operator *(const info &u,const info &v) {
		info w; w.d=(u.d+v.d)%m;
		for(int i=0;i<m;++i) w.f[i]=comb(u.f[i],v.f[(i+u.d)%m]);
		return w;
	}
};
info ksm(info a,ll b) { info s; for(;b;a=a*a,b>>=1)	if(b&1) s=s*a; return s; }
info euclid(ll N,ll P,ll Q,ll R,info X,info Y) {
	if((LL)P*N+R<Q) return ksm(Y,N);
	if(P>=Q) return euclid(N,P%Q,Q,R,X,ksm(X,P/Q)*Y);
	ll M=((LL)P*N+R)/Q;
	return ksm(Y,(Q-R-1)/P)*X*euclid(M-1,Q,P,(Q-R-1)%P,Y,X)*ksm(Y,N-((LL)Q*M-R-1)/P);
}
int rt[MAXN*2],lim;
void upd(ll x,int z,int q,int &p) {
	siz[p=++tot]=siz[q];
	if(siz[p]==1) return f[p]={z,1,z,1},void();
	if(x<=siz[ls[q]]) upd(x,z,ls[q],ls[p]),rs[p]=rs[q];
	else upd(x-siz[ls[q]],z,rs[q],rs[p]),ls[p]=ls[q];
	f[p]=f[ls[p]]+f[rs[p]];
}
int merge(int p,int q) {
	if(p<=lim||q<=lim) return max(p,q);
	ls[p]=merge(ls[p],ls[q]),rs[p]=merge(rs[p],rs[q]);
	f[p]=f[ls[p]]+f[rs[p]];
	return p;
}
void exgcd(ll a,ll b,ll &x,ll &y) {
	if(!b) x=1,y=0;
	else exgcd(b,a%b,y,x),y-=x*(a/b);
}
ll inv(ll u,ll p){
	ll a,b; exgcd(u,p,a,b);
	return (a%p+p)%p;
}
signed main() {
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>n>>m>>d>>q1>>q2;
	for(int i=1,x;i<=m;++i) cin>>x,f[i]={x,1,x,1},siz[i]=1;
	info X,Y,Z;
	X.d=(m-n%m)%m,Y.d=d%m,tot=m;
	for(int i=0;i<m;++i) Y.f[i]=i+1;
	rt[0]=euclid(n,d,n,0,X,Y).f[d%m];
	cout<<f[rt[0]].val()<<"\n",lim=tot;
	ll iv=inv(d,n);
	for(int i=1;i<=q1;++i) {
		ll x,y; cin>>x>>y,x=(LL)x*iv%n;
		upd(x?x:n,y,rt[0],rt[i]);
		cout<<f[rt[i]].val()<<"\n";
	}
	for(int i=q1+1,x,y;i<=q1+q2;++i) {
		cin>>x>>y;
		rt[i]=merge(rt[x],rt[y]);
		cout<<f[rt[i]].val()<<"\n";
	}
	return 0;
}