题目大意
有一个 \(n+1\times m+1\) 的网格。对于每一行 \(i\)，都要将左侧的一些格子 \((i,1),(i,2),\ldots,(i,x)\) 涂黑，其中 \(x = k\) 的概率为 \(a_{i,k}\)。同理对于每一列 \(j\)，都要将上方的一些格子 \((1,j),(2,j),\ldots,(x,j)\) 涂黑，其中 \(x = k\) 的概率为 \(b_{k,j}\)。求图中连通块的期望个数。
题解
发现本题中 \((1,1)\sim(n,1)\) 以及 \((1,1)\sim(1,m)\) 一定涂黑，于是所有的黑格子一定在一个连通块内，所以只要考虑白格子即可。
发现本题中白色的连通块一定存在一个最右下的白色格子，使得该连通块内所有格子均在其左侧、上方或左上方。于是，我们只需要算出每个格子成为这个右下格子的概率，加起来再加 \(1\) 就是白色连通块的期望数（加 \(1\) 是因为 \((n+1,1)\sim (n+1,m+1)\) 以及 \((1,m+1)\sim (n+1,m+1)\) 构成了一个白色连通块）。
考虑如何求出每个格子作为左下格子的期望。发现对于一个格子 \((i,j)\)，其作为左下格子，当且仅当：第 \(i\) 行和第 \(j\) 列都没染到该格子，且第 \(i+1\) 行和第 \(j+1\) 列都染过了该格子。这些都可以把概率数组前缀和搞定。
#include<iostream>
#include<cstdio>
#define maxn 1005
#define ll long long
#define mod 998244353
using namespace std;
int n,m; ll h[maxn][maxn],v[maxn][maxn],ans=0;
int main(){
//freopen("photo.in","r",stdin); freopen("photo.out","w",stdout);
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) for(int j=1;j<=m;j++){scanf("%lld",&h[i][j]); h[i][j]=(h[i][j]+h[i][j-1])%mod;}
for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) scanf("%lld",&v[i][j]);
for(int j=1;j<=m;j++) for(int i=1;i<=n;i++) v[i][j]=(v[i][j]+v[i-1][j])%mod;
for(int i=1;i<=n;i++) for(int j=1;j<=m;j++)
ans=(ans+h[i][j-1]*v[i-1][j]%mod*(h[i+1][n]-h[i+1][j-1]+mod)%mod*(v[n][j+1]-v[i-1][j+1]+mod)%mod)%mod;
printf("%lld",ans+2); return 0;
}