ARC114 - Paper Cutting 2

ARC114 - Paper Cutting 2

题目大意:

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

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

问期望多少步停止



(如果你熟练掌握概率的独立性,这道题非常简单)

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

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

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

也就是说,概率就是:

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

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

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);
}
上一篇:CF1514E - Baby Ehab's Hyper Apartment


下一篇:使用Epubor Ultimate将Kindle电子书导出为PDF(仅Windows)