[数学记录]ARC114E Paper Cutting 2

**题意** ：在一张方格图上有两个格子被染黑，每次操作选择一条两行或者两列之间的线将图切开。 如果两个黑格子被分开，则停止，否则将包含黑格的一部分保留，继续切。 求期望操作次数。 坐标范围 $\leq 10^5$ ，时限$\texttt{2s}$。 ------------ 对每条线计算 考虑鞭尸的套路，操作过程可以等效为：随机一个线的排列，依次考虑，若没有切在黑格所在的块，则不生效。直到有一条边切开黑格，则停止。 最终一定有一条切开黑格的边，对答案的贡献是 $1$。对于其余没切开黑格的边，分别计算生效的概率，求和就是答案。 将边分为五类，切开黑格的边 / 黑格上下左右的边。 对于黑格右侧的某条边，黑格上下左的边如何切割并不会影响其是否能生效。 只需要满足这条边左侧的同类边没有已切割，且切开黑格的边也均没有切割。 数一数这些边的总数 $c$（包括自身），概率就是 $1/c$ 。 复杂度 $O(V)$。 ```cpp #include<algorithm> #include<cstdio> #define MaxN 200500 using namespace std; const int mod=998244353; int H,W,h1,w1,h2,w2,inv[MaxN]; int main() { scanf("%d%d%d%d%d%d",&H,&W,&h1,&w1,&h2,&w2); if (h1>h2)swap(h1,h2);if (w1>w2)swap(w1,w2); inv[1]=1;for (int i=2;i<=H+W;i++)inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod; int ans=1,k=(h2-h1)+(w2-w1); for (int i=1;i<=H-h2;i++)ans=(ans+inv[i+k])%mod; for (int i=1;i<=h1-1;i++)ans=(ans+inv[i+k])%mod; for (int i=1;i<=W-w2;i++)ans=(ans+inv[i+k])%mod; for (int i=1;i<=w1-1;i++)ans=(ans+inv[i+k])%mod; printf("%d",ans); return 0; } ```