P12488 题解

· · 题解

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;
}