题解 CF712E 【Memory and Casinos】

· · 题解

题目

原题目-CF712E

传送门

考场题目-HearthStone

Description

　　“低保不是挺轻松的吗？”

　　HS 需要智商，需要知己知彼，需要根据场面情况和对手策略进行针对性的概率分析和分类讨论。zzh 不擅长这些，看着hzy 又一次低保，便向 hzy 请教经验。

　　“每次你与对手博弈，获胜一局加一分，否则扣一分。低保之后，连胜附加分取消，上分的道路更加艰难。”，说着hzy 拿出一张足有七十米长的小纸条，“这是根据目前天梯上的情况得到的，我的卡组在已有 i 分时找对手博弈获胜的概率。”

　　zzh 顿时来了劲，不停地问hzy，如果hzy 有一只小号目前有 l 分，不停地博弈，博弈过程中任何时刻不低于 l 分，最终到达 r 分的概率。因为天梯实况不时会改变，hzy还会不断地对纸条进行修改。于是，zzh 的问题就要你来回答了。

　　为了避免精度问题，请输出在模P＝998244353 域下的结果。

Input

　　第一行输入两个数，低保以上的分数上限 N，修改和询问总数 Q(N,Q≤10^5) 。

　　接下来 N 行，第 i+1 行两个数 x[i],y[i](1≤x[i]＜y[i]＜P) ，表示已有 i 分时获胜的概率为x[i]/y[i] 。

　　接下来 M 行，每行以下面的格式描述一个操作：

Output

　　对于所有zzh 的询问，一行一个数输出结果。

Sample Input

3 7
1 3
1 2
2 3
2 1 1
2 1 2
2 1 3
1 2 2 3
2 1 1
2 1 2
2 1 3

Sample Output

332748118
598946612
166374059
332748118
748683265
887328314

Hint

测试点编号 分值 对 N 和 Q 的限制 其他限制
1 3 N=1 无
2 22 N\le 3,Q\le 10 无
3 19 N\le 1000,Q\le 1000 无
4 24 无 无操作1，所有 y[i] 相同
5 6 无 无
6 26 无 无

如果P 是质数，那么 Q^{(P-1)}≡1\ (mod P) 。

题解

注：本题考场题面与原题面不同，故考场思路中有些细节与原题不同，但是思路应该可取。

考场思路

可以将题目简化一下：

  • 在一段有 n 个的连续的格子上，第 i 个格子向右走的概率为 p_i=\frac{x_i}{y_i} （显然向左走的概率为 1-p_i），现在给出 Q 个询问或修改，修改会修改点 d 的 p_d 值，询问会询问从 l 开始，不经过 l-1 到 r+1 的概率。

显然的一道概率 DP。

考虑当 l=r 时，直接输出 x[i]\times \text{inv}(y[i])，然后这样就有 3pts 了...

更好的方案，设 f[i] 为从 l 合法地走到 i 的概率，显然有初始化（而不是概率）

\color{red}{f[l]=1+f[l+1]\times failed[l+1]}

注意，上式中的 f[l] 并不是概率，而是一个初始化。

其中 failed[l+1] 为从 l+1 向左走的概率。

并且，还有

\begin{align} f[i]=win[i-1]\times f[i-1]+failed[i+1]\times f[i+1],i\neq l,i\neq r \tag{1} \end{align}

其中，win[i] 表示从 i 走到 i+1 的概率。

那么，我们将 i=l+1 带入上式，可得

f[l+1]=win[l]+win[l]failed[l+1]f[l+1]+failed[l+2]f[l+2]

我们移项之后有一个式子

f[l+1]=\frac{win[l]}{1-win[l]failed[l+1]}+\frac{failed[l+2]}{1-win[l]failed[l+1]}f[l+2]

这个式子中，前一项是常数项，我们不妨将其看做 a，而后一项的系数我们也可以看出来，不放将其看做 b，然后就有

f[l+1]=a+b\times f[l+2]

令 i=l+2，那么就是

f[i-1]=a+b\times f[i]

又是一个关于 i 和 i-1 的式子，将其带入 (1)，我们又可以得到一个关于 f[i] 和 f[i+1] 的式子，令 i'=i+1，那么那个式子变成 f[i'-1] 和 f[i'] 的关系式。

发现可以迭代，迭代到 i'=r-1 时，得到 f[r-1] 和 f[r] 的关系，然后结合

f[r]=f[r-1]\times win[r-1]

可以解得 f[r]，而最后的答案就是 f[r]\times win[r] 了。

由于是线性递推，这个方法 \mathcal O(NQ)，期望 44pts，结果 44pts。

考场代码

/* 44pts */

#include<cstdio>

#define cg (c=getchar())
inline int read(){
    int x;bool f=true;char c;
    while(cg<'0' || '9'<c)if(c=='-')f=false;
    for(x=(c^48);'0'<=cg && c<='9';x=(x<<1)+(x<<3)+(c^48));
    return f?x:-x;
}
#undef cg

const int MOD=998244353;
const int MAXN=1e5;

inline int inv(int x,int n=MOD-2){
    int ret=1;
    for(;n>0;n>>=1){
        if(n&1)ret=1ll*ret*x%MOD;
        x=1ll*x*x%MOD;
    }return ret;
}

int f[MAXN+5];
int win[MAXN+5],fail[MAXN+5];
int N,Q;

inline void Init(){
    N=read(),Q=read();
    int x,y;
    for(int i=1;i<=N;++i){
        x=read(),y=read();
        win[i]=1ll*x*inv(y)%MOD;
        fail[i]=1ll*(y-x)*inv(y)%MOD;
    }
}

inline void solve1(){
    int opt,d,l,r;
    int a,b;
    while(Q--){
        opt=read();
        if(opt==1){
            d=read(),l=read(),r=read();
            win[d]=1ll*l*inv(r)%MOD;
            fail[d]=1ll*(r-l)*inv(r)%MOD;
        }else{
            l=read(),r=read();
            if(l==r){printf("%d\n",win[l]);continue;}
            a=1,b=fail[l+1];
            for(int i=l+1;i<=r;++i){
                a=1ll*a*win[i-1]%MOD,b=1ll*b*win[i-1]%MOD;
                b=(MOD+1-b)%MOD;
                a=1ll*a*inv(b)%MOD;
                /*if(i<r)*/b=1ll*fail[i+1]*inv(b)%MOD;
            }
            // a=1ll*a*win[r-1]%MOD,b=1ll*b*win[r-1]%MOD;
            // b=(MOD+1-b)%MOD;
            // a=1ll*a*inv(b)%MOD;
            printf("%lld\n",1ll*a*win[r]%MOD);
        }
    }
}

signed main(){
    // freopen("hs.in","r",stdin);
    // freopen("hs.out","w",stdout);
    Init();
    solve1();
    return 0;
}
/*

O(NQ):线性递推
O(Q logN):加上一些数据结构优化 ?

*/

正解

定义 f[i] 为从 i 合法地走到 r+1 的概率，显然有 f[r+1]=1,f[l-1]=0，并且有一个关系式

\begin{aligned} &f[i]=f[i-1]\times (1-p[i])+f[i+1]\times p[i] \\ \Rightarrow &f[i]=f[i-1]-p[i]f[i-1]+f[i+1]p[i] \\ \Rightarrow &f[i]-f[i-1]=p[i](f[i+1]-f[i-1]) \end{aligned}

然后我们定义 g[i]=f[i]-f[i-1]，那么上式可以化为

\begin{aligned} &g[i]=p[i](g[i+1]+g[i]) \\ \Rightarrow &\frac{1-p[i]}{p[i]}g[i]=g[i+1] \end{aligned}

得到了递推式，现在看我们要求什么？

答案显然是 f[l] 了，并且我们有

\begin{aligned} 1-0&=f[r+1]-f[l-1] \\ &=\sum_{i=l}^{r+1}g[i] \\ \end{aligned}

而我们又有 g[i+1]=\frac{1-p[i]}{p[i]}g[i]，那么我们可以将所有的 g[i] 用 g[l] 表示出来，那么原式可以写作

\sum_{i=l}^{r+1}g[l]\prod_{j=l}^{i-1}\frac{1-p[j]}{p[j]}

特殊规定：当 i-1<l 时，\prod_{j=l}^{i-1}\frac{1-p[j]}{p[j]}=1。

整理一下，我们就有

1=g[l]\sum_{i=l}^{r+1}\prod_{j=l}^{i-1}\frac{1-p[j]}{p[j]}

将 g[l] 的系数移项过去，我们可以快乐地解得 g[l] 的值，而 g[l] 有什么用？

由定义，有

g[l]=f[l]-f[l-1]=f[l]-0=f[l]=\text{Ans}

那么，我们现在唯一的问题就是 \sum_{i=l}^{r+1}\prod_{j=l}^{i-1}\frac{1-p[j]}{p[j]} 这一坨怎么维护了。

定义 t[i]=\frac{1-p[i]}{p[i]}

由于我们对于这个式子有一个特殊规定，使得这个式子不是那么的规则，我们考虑将这个特殊规定的 1 提出来，就有

\sum_{i=l}^{r+1}\prod_{j=l}^{i-1}t[j]=1+\sum_{i=l}^{r}\prod_{j=l}^{i}t[j]

这个式子现在看上去很整齐了，但是我们怎么维护？

考虑将后面那一项变换为前缀作差形式，用补项思想，那么有

\begin{aligned} \left( \prod_{i=1}^{l-1}t[i] \right)\times \sum_{i=l}^{r}\prod_{j=l}^{i}t[j]=\sum_{i=1}^r\prod_{j=1}^it[j]-\sum_{i=1}^{l-1}\prod_{j=1}^it[j] \end{aligned}

那么就有

\sum_{i=l}^{r}\prod_{j=l}^{i}t[j]=\frac{\sum_{i=1}^r\prod_{j=1}^it[j]-\sum_{i=1}^{l-1}\prod_{j=1}^it[j]}{\prod_{i=1}^{l-1}t[i]}

现在全部都是前缀的形式了，我们只需要维护 \sum_{i=1}^r\prod_{j=1}^it[j] 与 \prod_{i=1}^{l-1}t[i] 即可。

正解代码

被我咕掉了qwq