题解

要求最大值，所以考虑\(min-max\)

\[ \max(S)=\sum_{T|S}\min(T)^{|T|+1} \]

那么一个集合的\(min\)如何求呢，我们一共有\(n*(m-1)+m*(n-1)\)个相邻的对，令该集合涉及到的相邻的对的个数为\(x\),那么期望的时间为\(\frac{n*(m-1)+m*(n-1)}{x}\)。

所以我们可以在轮廓线上\(dp\)，设\(dp[i][j][s][num]\)表示做到了\((i,j)\),当前状态为\(s\),有\(num\)个相邻对。

我们\(dp\)的内容是系数和，最后根据不同的\(num\)再乘上个系数就行了。

因为拐角的状态不用记，所以好写一些。

代码

#include
    
     #define N 7#define M 103using namespace std;typedef long long ll;const int mod=998244353;int n,m;char a[N][M];ll dp[2][1<<6][N*M*2],ans;inline ll power(ll x,ll y){    ll ans=1;    while(y){        if(y&1)ans=ans*x%mod;        x=x*x%mod;        y>>=1;    }    return ans;}inline void MOD(ll &x){x=x>=mod?x-mod:x;}inline ll ni(ll x){return power(x,mod-2);}int main(){    scanf("%d%d",&n,&m);    for(int i=1;i<=n;++i){        scanf("%s",a[i]+1);    }    int sum=n*m*2-n-m;    int now=1,pre=0;    dp[now][0][0]=mod-1;    int maxn=(1<