jzoj5837 Omeed 线段树+矩阵乘法

Description

---

好长啊

Solution

---

早上睡过头了推出一堆假的柿子并不能过样例

考虑怎么求c(i)的期望。显然有ci=(ci−1+1)×pi+ci−1×t×(1−pi)$c_i=\left(c_{i-1}+1\right)\times p_i+c_{i-1}\times t\times \left(1-p_i\right)$
再考虑求combo分数的期望。显然有comboi=comboi−1+(ci−1+1)×pi×B$comb{o}_i=comb{o}_{i-1}+\left(c_{i-1}+1\right)\times p_i\times B$
这里需要注意一下，只有当前i是perfect的情况才能拿贡献，因此第i位我们要钦定为perfect
然后就能拿到50+pts

考虑这么一类问题：我们知道一个dp柿子，现在有多组询问要求以不同位置作为起点做dp。
我们可以求出dp的转移矩阵，对于给定的起点求出初始矩阵，对于询问区间我们用线段树维护转移矩阵的区间积
那么做法就非常显然了。注意到我们的转移矩阵只有3*3，部分位置始终为0且部分位置始终为1，那么我们可以优化矩阵乘法的过程来底ka层chang优shu化

Code

---

#include <stdio.h>
#include <string.h>
#include <algorithm>
#define rep(i,st,ed) for (int i=st;i<=ed;++i)
#define fill(x,t) memset(x,t,sizeof(x))
#define lowbit(x) ((x)&(-(x)))

typedef long long LL;
const int MOD=998244353;
const int N=500005*4;

struct Matrix {
    LL arr[3][3];
} t[N],ret;

int n,q,ta,tb;
LL p[N],A,B,tt;

int read() {
    int x=0,v=1; char ch=getchar();
    for (;ch<'0'||ch>'9';v=(ch=='-')?(-1):(v),ch=getchar());
    for (;ch<='9'&&ch>='0';x=x*10+ch-'0',ch=getchar());
    return x*v;
}

void write(int x) {
    if (x>9) write(x/10);
    putchar(x%10+'0');
}

inline LL ksm(LL x,LL dep) {
    LL ret=1;
    for (;dep;) {
        ret=ret*((dep&1)?(x):(1))%MOD;
        x=x*x%MOD; dep>>=1;
    }
    return ret;
}

inline void mul(Matrix &c,Matrix a,Matrix b) {
    c.arr[0][0]=a.arr[0][0]*b.arr[0][0]%MOD;
    c.arr[0][1]=(a.arr[0][0]*b.arr[0][1]+a.arr[0][1])%MOD;

    c.arr[1][1]=c.arr[2][2]=1;

    c.arr[2][0]=(a.arr[2][0]*b.arr[0][0]+b.arr[2][0])%MOD;
    c.arr[2][1]=(a.arr[2][0]*b.arr[0][1]%MOD+a.arr[2][1]+b.arr[2][1])%MOD;
}

inline void modify(int now,int tl,int tr,int x,LL v) {
    if (tl==tr) {
        p[tl]=v;
        t[now].arr[0][0]=(v+tt-v*tt%MOD+MOD)%MOD;
        t[now].arr[0][1]=B*v%MOD;
        t[now].arr[2][0]=v;
        t[now].arr[2][1]=v*(A+B)%MOD;
        t[now].arr[1][1]=t[now].arr[2][2]=1;
        return ;
    }
    int mid=(tl+tr)>>1;
    if (x<=mid) modify(now<<1,tl,mid,x,v);
    else modify(now<<1|1,mid+1,tr,x,v);
    mul(t[now],t[now<<1],t[now<<1|1]);
}

inline Matrix query(int now,int tl,int tr,int l,int r) {
    if (tl==l&&tr==r) return t[now];
    int mid=(tl+tr)>>1;
    if (r<=mid) return query(now<<1,tl,mid,l,r);
    if (l>mid) return query(now<<1|1,mid+1,tr,l,r);
    Matrix qx=query(now<<1,tl,mid,l,mid);
    Matrix qy=query(now<<1|1,mid+1,tr,mid+1,r);
    mul(ret,qx,qy);
    return ret;
}

void build(int now,int tl,int tr) {
    if (tl==tr) {
        LL v=p[tl];
        t[now].arr[0][0]=(v+tt-v*tt%MOD+MOD)%MOD;
        t[now].arr[0][1]=B*v%MOD;
        t[now].arr[2][0]=v;
        t[now].arr[2][1]=v*(A+B)%MOD;
        t[now].arr[1][1]=t[now].arr[2][2]=1;
        return ;
    }
    int mid=(tl+tr)>>1;
    build(now<<1,tl,mid);
    build(now<<1|1,mid+1,tr);
    mul(t[now],t[now<<1],t[now<<1|1]);
}

int main(void) { 
    freopen("omeed.in","r",stdin);
    freopen("omeed.out","w",stdout);
    read(),n=read(),q=read();
    ta=read(),tb=read(),A=read(),B=read();
    tt=ta*ksm(tb,MOD-2)%MOD;
    rep(i,1,n) {
        LL x=read(),y=read();
        p[i]=x*ksm(y,MOD-2)%MOD;
    }
    build(1,1,n);
    for (;q--;) {
        int opt=read(),l,r,ans;
        if (opt) {
            l=read(),r=read();
            Matrix ret=query(1,1,n,l,r);
            ans=ret.arr[2][1]%MOD;
            write(ans); putchar('\n');
        } else {
            int x=read(),up=read(),down=read();
            LL tmp=1LL*up*ksm(down,MOD-2)%MOD;
            modify(1,1,n,x,tmp);
        }
    }
    return 0;
}