题目大意
有一个矩形，上面有若干个关键点，每次随机一个相邻的位置，问全部关键点被选取的期望时间
思路
设每个关键点被选取的时间为 \(t_i\) ，则答案就为 \(E(max(t_i))\)
然后我们发现 \(E(min(t_i))\) 是好求的，只需要保证在此之前全部都不被选即可，所以可以 \(min-max\) 容斥， \(ans=\sum_{S\subset U,S \not=\emptyset}(-1)^{|S|-1}E(min_{i\in S}(t_i))\)
设选到任意一个关键点的方案数为 \(C\) ，总选法为 \(A\)，则 \(E(min(t_i))=\frac{A}{C}\)
于是我们可以考虑用这玩意 \(DP\)，设 \(f_{i,j,S,C}\) 表示现在 \(DP\) 到 \((i,j)\)，上一层轮廓状态为 \(S\)，选中的方案数为 \(C\)，正常转移即可
复杂度 \(O(n^2m^22^{nm})\)
code
#include<bits/stdc++.h>
using namespace std;
#define N 105
#define int long long
int n,m,tot,ans,A,ALL;
const int mod=998244353;
int id[N][N],f[605][70][1205];
char mp[N][N];
int ksm(int x,int y){
int ans=1;
while(y){
if(y&1) ans=ans*x%mod;
x=x*x%mod,y>>=1;
}
return ans;
}
int yi(int S,int x){
if(!x) return 1;
return (S>>(x-1))&1;
}
int shan(int S,int x){
return S&(ALL^(1<<(x-1)));
}
int tian(int S,int x){
return S|(1<<(x-1));
}
void mo(int &x){
x=(x%mod+mod)%mod;
}
signed main(){
freopen("destroy.in","r",stdin);
freopen("destroy.out","w",stdout);
scanf("%lld%lld",&n,&m);
for(int i=1;i<=n;i++) scanf("%s",mp[i]+1);
for(int j=1;j<=m;j++){
for(int i=1;i<=n;i++) id[i][j]=++tot;
}
ALL=(1<<n)-1;
if(mp[1][1]=='.') f[id[1][1]][ALL^1][0]=mod-1;
else f[id[1][1]][ALL^1][0]=mod-1,f[id[1][1]][ALL][2-(n==1)-(m==1)]=1;
A=2*n*m-n-m;
for(int j=1;j<=m;j++){
for(int i=1;i<=n;i++){
if(i==1&&j==1) continue;
int now=id[i][j],las=id[i][j]-1;
for(int S=0;S<=ALL;S++){
for(int c=0;c<=A;c++) f[now][shan(S,i)][c]+=f[las][S][c],mo(f[now][shan(S,i)][c]);
if(mp[i][j]=='.') continue;
int cnt=4-(i==n)-(j==m)-yi(S,i-1)-yi(S,i);
for(int c=0;c<=A-cnt;c++) f[now][tian(S,i)][c+cnt]-=f[las][S][c],mo(f[now][tian(S,i)][c+cnt]);
}
}
}
for(int c=1;c<=A;c++){
int bas=A*ksm(c,mod-2)%mod;
for(int S=0;S<=ALL;S++) ans+=f[id[n][m]][S][c]*bas,mo(ans);
}
printf("%lld\n",ans);
return 0;
}