AT_arc114_e [ARC114E] Paper Cutting 2

可以先完成：AT_agc049_a Erasing Vertices

一个 trick

E ( X ) = ∑ i = 1 n x i p i E(X)=\sum_{i=1}^n x_i p_iE(X)=i=1∑n​xi​pi​
上面是期望的定义式。对于这种题目，每次切纸对答案步数的贡献都固定为1 11，所以上面的式子可以变成：
E ( X ) = ∑ i = 1 n p i E(X)=\sum_{i=1}^n p_iE(X)=i=1∑n​pi​
所以现在的问题变成了求每条线被选中的概率之和。

思路

定义线i ii为第i ii行与第i + 1 i+1i+1行之间的线，j jj为第j jj列和第j + 1 j+1j+1列之间的线。

一条线不被选中只有两种情况：

1. 操作已经结束了，它还没有被选过。
2. 操作还没有结束，但它被分到了不含两个黑格的那张纸上。

考虑对于每一条线，求出有多少根线选了会使这根线不能再选（包括它自己）。

假设这样的线有l e n lenlen根。在第一次切到这些线中的某一条之前，它们地位相同，所以目标线最先被切到的概率是1 l e n \frac{1}{len}len1​。

我们用l e n i len_ileni​表示可以影响到线i ii的线数量，l e n j len_jlenj​表示可以影响到线j jj的线的数量。

最终的答案就是：
∑ i = 1 H − 1 1 l e n i + ∑ j = 1 W − 1 1 l e n j \sum_{i=1}^{H-1}\frac{1}{len_i}+\sum_{j=1}^{W-1}\frac{1}{len_j}i=1∑H−1​leni​1​+j=1∑W−1​lenj​1​

现在需要计算l e n i len_ileni​和l e n j len_jlenj​。

考虑第一种情况，只要选中了两个黑点之间的线，操作就会结束，所以l e n i len_ileni​和l e n j len_jlenj​的基础是两个黑点之间的切割线总数。

对于第二种情况，我们再分成两种情况讨论。

1. 若当前线在两黑点之间，会影响的就是两黑点之间线的数量。
2. 否则，就是两黑点之间线的数量加上这条线距离最近的黑点的距离。

code

#include<bits/stdc++.h>#defineintlonglong//#define lc p<<1//#define rc p<<1|1#defineendlputchar('\n')#definepspputchar(' ')usingnamespacestd;typedefunsignedlonglongull;typedeflonglongll;constintmod=998244353;constintN=1e5+5;intread(){intx=0,f=1;charc=getchar();while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+c-'0',c=getchar();returnx*f;}voidprint(intx){if(x<0)putchar('-'),x=-x;if(x<10){putchar(x+'0');return;}print(x/10);putchar(x%10+'0');}voidputstr(string s){for(inti=0;i<s.size();i++)putchar(s[i]);}intlowbit(intx){returnx&-x;}intn,m,k;intT;//x 表示 x~x+1 中间的线intcutx[N];intcuty[N];intdepx[N];intdepy[N];intdepxx[N];intdepyy[N];intcanx;intcany;intpoww(inta,intb){intres=1;while(b){if(b&1)res=(res*a)%mod;a=(a*a)%mod;b>>=1;}returnres;}signedmain(){//ios::sync_with_stdio(0);n=read(),m=read();intx=read(),y=read();intxx=read(),yy=read();for(inti=min(x,xx);i<=max(x,xx)-1;i++)cutx[i]=1,canx++;for(inti=min(y,yy);i<=max(y,yy)-1;i++)cuty[i]=1,cany++;for(inti=max(x,xx);i<n;i++)depx[i]=depx[i-1]+1;for(inti=max(y,yy);i<m;i++)depy[i]=depy[i-1]+1;for(inti=min(x,xx)-1;i>=1;i--)depxx[i]=depxx[i+1]+1;for(inti=min(y,yy)-1;i>=1;i--)depyy[i]=depyy[i+1]+1;intres=0;for(inti=1;i<n;i++)(res+=poww(max(depx[i],depxx[i])+canx+cany,mod-2))%=mod;for(inti=1;i<m;i++)(res+=poww(max(depy[i],depyy[i])+canx+cany,mod-2))%=mod;print(res%mod);}