ARC114 - Paper Cutting 2

题目大意：

在一张方格图上确定了一个矩形，每次操作选择一条两行或者两列之间的线将图切开

如果切开了矩形就停止，否则将包含矩形的一部分保留

问期望多少步停止



（如果你熟练掌握概率的独立性，这道题非常简单）

称矩形内部的横竖线为关键线

考虑对于每一个横线|竖线计算其被切的概率，以矩形右边的一条竖线为例

那么在这条竖线右边的线，以及在矩形左边的线，矩形上下的横线 都与其独立

也就是说，概率就是：

这条竖线左边且在矩形右边的线和所有关键线之中，这条线是第一个被切掉的概率

那么数一下上面提到所有线的个数$c$，概率就是$\frac{1} {c}$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

const int N=2e5+10,P=998244353;

int n,m;
int I[N];
int a,b,c,d;

int main(){
	I[0]=I[1]=1;
	rep(i,2,N-1) I[i]=1ll*(P-P/i)*I[P%i]%P;
	n=rd(),m=rd();
	a=rd(),b=rd(),c=rd(),d=rd();
	if(a>c) swap(a,c);
	if(b>d) swap(b,d);
	int e=c-a+d-b,ans=1;
	rep(i,1,a-1) ans=(ans+I[a-i+e])%P;
	rep(i,c+1,n) ans=(ans+I[i-c+e])%P;
	rep(i,1,b-1) ans=(ans+I[b-i+e])%P;
	rep(i,d+1,m) ans=(ans+I[i-d+e])%P;
	printf("%d\n",ans);
}