题目

原题目-CF712E

传送门

考场题目

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\) 行，每行以下面的格式描述一个操作：

• \(1\ d\ x\ y (1≤d≤N,1≤x＜y＜P)\)：hzy 将已有 \(d\) 分时获胜的概率改为 \(x/y\)；

• \(2\ l\ r\ (1≤l≤r≤N)\)：zzh 进行一次询问，询问的含义如题。

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

如果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\) 的概率，显然有初始化（而不是概率）

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

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

并且，还有

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

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

我们移项之后有一个式子

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

令 \(i=l+2\)，那么就是

又是一个关于 \(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]\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\)，并且有一个关系式

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

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

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

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

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

整理一下，我们就有

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

由定义，有

那么，我们现在唯一的问题就是 \(\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=1}^r\prod_{j=1}^it[j]\) 与 \(\prod_{i=1}^{l-1}t[i]\) 即可。

正解代码

被我咕掉了qwq

[CF712E]Memory and Casinos

原文：https://www.cnblogs.com/Arextre/p/13160459.html