Ender的模拟赛D2T1 wait【min-max反演】

题目描述

有一n*m的棋盘,每次随机染黑一个位置(可能染到已经黑了的),当某一行或者一列全为黑色时停止,求期望染色次数(mod 998244353)
对于100%的数据n,m<=1000

题目分析

考完听说是模板题
显然这个“当xxx时停止”非常不好处理，我们不知道它到底有没有停止，方案也很难统计。
不考虑停止，一直染，用$a_1,a_2\dots a_n$表示$a_i$行全黑时的次数，用$b_j$表示$b_j$列全黑时的次数。
我们想知道 E ( min ⁡ { a 1 , a 2 … a n , b 1 , b 2 … b m } ) E\left(\min\{a_1,a_2\dots a_n,b_1,b_2\dots b_m\}\right) E(min{a1​,a2​…an​,b1​,b2​…bm​})
上minmax反演：
$$\min (S)=\sum _{T\subseteq S,T̸=\varnothing }(-1{)}^{|T|-1}\max (T)$$
证明：设$s_1\le s_2\cdots \le s_N$，考虑$s_i$在右式的贡献：$s_i$作为max,剩下的数在$s_1$到$s_{i-1}$随便选。当$i>1$时，集合数为$2^{i-1}$，集合奇偶各占一半，相互抵消；当$i=1$时，集合数为1，贡献为$s_1$，得证。
在外面套上一个期望，上式仍然成立。
选出$i$行，$j$列，$a,b$的max就是把这$i$行$j$列全部染黑的次数，总个数是$k=im+jn-ij$，染到第一个的概率是$\frac{k}{nm}$，期望次数就是$\frac{nm}{k}$，染第二个的期望次数就是$\frac{nm}{k-1}$。所以
$$E(\min (a..,b..))=\sum _{i=0}^n\sum _{j=0}^m[i||j]\left(\genfrac{}{}{0ex}{}{n}{i}\right)\left(\genfrac{}{}{0ex}{}{m}{j}\right)nm(1+\frac{1}{2}+...+\frac{1}{im+jn-ij})$$

附上minmax反演的学习

Code：

#include<bits/stdc++.h>
#define maxn 1005
using namespace std;
const int mod = 998244353;
int n,m,ans,c[maxn][maxn],inv[maxn*maxn],s[maxn*maxn];
int main()
{
	freopen("wait.in","r",stdin);
	freopen("wait.out","w",stdout);
	scanf("%d%d",&n,&m);
	c[0][0]=1;
	for(int i=1;i<=max(n,m);i++){
		c[i][0]=c[i][i]=1;
		for(int j=1;j<i;j++) 
			c[i][j]=(c[i-1][j-1]+c[i-1][j])%mod;
	}
	inv[0]=inv[1]=1,s[1]=n*m;
	for(int i=2;i<=n*m;i++) 
		inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod,
		s[i]=(s[i-1]+1ll*n*m*inv[i])%mod;
	for(int i=0;i<=n;i++)
		for(int j=0;j<=m;j++) if(i||j)
			ans=(ans+1ll*((i+j)&1?1:-1)*c[n][i]*c[m][j]%mod*s[i*m+j*n-i*j])%mod;
	printf("%d\n",(ans+mod)%mod);
}