可以先完成AT_agc049_a Erasing Vertices一个 trickE ( X ) ∑ i 1 n x i p i E(X)\sum_{i1}^n x_i p_iE(X)i1∑n​xi​pi​上面是期望的定义式。对于这种题目每次切纸对答案步数的贡献都固定为1 11所以上面的式子可以变成E ( X ) ∑ i 1 n p i E(X)\sum_{i1}^n p_iE(X)i1∑n​pi​所以现在的问题变成了求每条线被选中的概率之和。思路定义线i ii为第i ii行与第i 1 i1i1行之间的线j jj为第j jj列和第j 1 j1j1列之间的线。一条线不被选中只有两种情况操作已经结束了它还没有被选过。操作还没有结束但它被分到了不含两个黑格的那张纸上。考虑对于每一条线求出有多少根线选了会使这根线不能再选包括它自己。假设这样的线有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_{i1}^{H-1}\frac{1}{len_i}\sum_{j1}^{W-1}\frac{1}{len_j}i1∑H−1​leni​1​j1∑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​的基础是两个黑点之间的切割线总数。对于第二种情况我们再分成两种情况讨论。若当前线在两黑点之间会影响的就是两黑点之间线的数量。否则就是两黑点之间线的数量加上这条线距离最近的黑点的距离。code#includebits/stdc.h#defineintlonglong//#define lc p1//#define rc p1|1#defineendlputchar(\n)#definepspputchar( )usingnamespacestd;typedefunsignedlonglongull;typedeflonglongll;constintmod998244353;constintN1e55;intread(){intx0,f1;charcgetchar();while(c0||c9){if(c-)f-1;cgetchar();}while(c0c9)x(x3)(x1)c-0,cgetchar();returnx*f;}voidprint(intx){if(x0)putchar(-),x-x;if(x10){putchar(x0);return;}print(x/10);putchar(x%100);}voidputstr(string s){for(inti0;is.size();i)putchar(s[i]);}intlowbit(intx){returnx-x;}intn,m,k;intT;//x 表示 x~x1 中间的线intcutx[N];intcuty[N];intdepx[N];intdepy[N];intdepxx[N];intdepyy[N];intcanx;intcany;intpoww(inta,intb){intres1;while(b){if(b1)res(res*a)%mod;a(a*a)%mod;b1;}returnres;}signedmain(){//ios::sync_with_stdio(0);nread(),mread();intxread(),yread();intxxread(),yyread();for(intimin(x,xx);imax(x,xx)-1;i)cutx[i]1,canx;for(intimin(y,yy);imax(y,yy)-1;i)cuty[i]1,cany;for(intimax(x,xx);in;i)depx[i]depx[i-1]1;for(intimax(y,yy);im;i)depy[i]depy[i-1]1;for(intimin(x,xx)-1;i1;i--)depxx[i]depxx[i1]1;for(intimin(y,yy)-1;i1;i--)depyy[i]depyy[i1]1;intres0;for(inti1;in;i)(respoww(max(depx[i],depxx[i])canxcany,mod-2))%mod;for(inti1;im;i)(respoww(max(depy[i],depyy[i])canxcany,mod-2))%mod;print(res%mod);}