command_block 的博客

command_block 的博客

[数学记录]ARC114E Paper Cutting 2

posted on 2021-10-28 19:00:20 | under 记录 |

题意 :在一张方格图上有两个格子被染黑,每次操作选择一条两行或者两列之间的线将图切开。

如果两个黑格子被分开,则停止,否则将包含黑格的一部分保留,继续切。

求期望操作次数。

坐标范围 $\leq 10^5$ ,时限$\texttt{2s}$。


对每条线计算

考虑鞭尸的套路,操作过程可以等效为:随机一个线的排列,依次考虑,若没有切在黑格所在的块,则不生效。直到有一条边切开黑格,则停止。

最终一定有一条切开黑格的边,对答案的贡献是 $1$。对于其余没切开黑格的边,分别计算生效的概率,求和就是答案。

将边分为五类,切开黑格的边 / 黑格上下左右的边。

对于黑格右侧的某条边,黑格上下左的边如何切割并不会影响其是否能生效。

只需要满足这条边左侧的同类边没有已切割,且切开黑格的边也均没有切割。

数一数这些边的总数 $c$(包括自身),概率就是 $1/c$ 。

复杂度 $O(V)$。

#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;
}