- 一个(n imes m)的网格图，其中有一些关键点。
- 一次操作会随机选中相邻的一对点（一个点可能选中多次），求所有关键点都被选中的期望次数。
- (nle6,mle100)
(Min-Max)容斥
(Min-Max)容斥的基本公式：
[E(max(S))=sum_{Tsubseteq S}(-1)^{|T|-1}E(min(T))
]
因此，我们就可以把所有关键点都被选中的限制，转化为其中一个关键点被选中。
然而(n imes mle600)肯定不可能直接暴枚子集。
考虑(E(min(T)))，设(c(T))为包含至少一个(xin T)的相邻点对数，那么就有：
[E(min(T))=frac{n imes(m-1)+(n-1) imes m}{c(T)}
]
所以只要把(c(T))设入状态，然后(DP)计数即可。
简单的轮廓线(DP)计数
我们设(f_{i,j,k,p})表示(DP)到位置((i,j))，(c(T)=k)，前(n)个位置（轮廓线）选择状态为(p)时((-1)^{|T|-1})之和。
转移就考虑当前位置是否选择：
- 如果不选择，判断((i,j-1))和((i-1,j))是否存在及是否选择，选择则分别给(k)加上(1)，然后直接转移。
- 如果选择（当前点必须是关键点），判断((i,j-1))和((i-1,j))是否存在，存在则分别给(k)加上(1)，然后乘上(-1)的系数转移。
最后每个(c(T))对应的((-1)^{|T|-1})之和就应该是(sum_pf_{n,m,c(T),p})。
代码：(O(n^2m^22^n))
#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define Reg register
#define RI Reg int
#define Con const
#define CI Con int&
#define I inline
#define W while
#define N 6
#define M 100
#define X 998244353
#define Inc(x,y) ((x+=(y))>=X&&(x-=X))
using namespace std;
int n,m,f[N+5][M+5][N*M<<1][1<<N];char a[N+5][M+5];
I int QP(RI x,RI y) {RI t=1;W(y) y&1&&(t=1LL*t*x%X),x=1LL*x*x%X,y>>=1;return t;}
int main()
{
RI i,j,k,p,s,l;for(scanf("%d%d",&n,&m),s=n*(m-1)+(n-1)*m,l=1<<n,i=1;i<=n;++i) scanf("%s",a[i]+1);
RI x,y;for(f[1][1][0][0]=X-1,f[1][1][0][1]=a[1][1]=='*',j=1;j<=m;++j) for(i=1;i<=n;++i)//初始状态考虑(1,1)两种填法
if(x=i+1,y=j,x>n&&(x=1,++y),y<=m) for(k=0;k<=s;++k) for(p=0;p^l;++p) f[i][j][k][p]&&
(
Inc(f[x][y][k+(x^1&&p&1)+(y^1&&p>>n-1&1)][p<<1&(l-1)],f[i][j][k][p]),//如果当前位置不选择
a[x][y]=='*'&&(Inc(f[x][y][k+(x!=1)+(y!=1)][(p<<1&(l-1))|1],X-f[i][j][k][p]))//如果当前位置选择
);
RI t=0;for(k=1;k<=s;++k) for(p=0;p^l;++p) t=(t+1LL*s*QP(k,X-2)%X*f[n][m][k][p])%X;return printf("%d
",t),0;//根据c(T)统计答案
}