有一面由 $n\times m$ 个格子组成的墙，每个格子要么是黑色，要么是白色。你每次将会进行这样的操作：等概率随机选择一个位置 $(x,y)$，和一个颜色 $c$（黑色或者白色）（$1\le x\le n,1\le y\le m$，任意 $(x,y,c)$ 的组合选择它的概率均为 $\frac{1}{2\ast n\ast m}$），然后将在 $(x,y)$ 左上⻆的所有格子的颜色涂成 $c$。即将所有满足 $1\le x\prime \le x,1\le y\prime \le y$ 的 $(x\prime ,y\prime )$ 格子上的颜色涂成 $c$。这次操作的代价为涂的格子的数量，即 $x\times y$。给定初始状态和终止状态，问期望要花费多少代价才能将墙面从初始状态涂成终止状态。答案模 $998244353$。

$n,m\le 5$

---

先考虑朴素的 dp，对墙上的每个格子进行状态压缩，总共有 $2^{nm}$ 个状态，设 $f_i$ 表示状态 $i$ 期望还要花费多少代价才能到达最终状态。转移为
$$f_i=\sum \frac{f_j+w}{2nm}$$

其中 $j$ 表示一个格子的左上角都涂成黑色或白色所得到的状态，$w$ 是涂一次颜色的代价。

这是有后效性 dp，可以高斯消元解决，时间复杂度 $O(2^{3nm})$，可以得到 60pts。

下面考虑减少状态。

考虑一个状态，若一个格子的颜色与最终状态的颜色不同，则这个点后面一定会修改，其左上角的点同样，所以这些点的颜色是什么就不重要了，反正后面都要被改。记 $p_{i,j}$ 表示状态中坐标为 $(i,j)$ 的点的颜色是否（1/0）与终止状态一样，通过模拟可以发现，$p$ 数组中构成 $1$ 的元素是类似阶梯的形状。如下图，圆点表示在这个格子颜色与最终状态的不一样，矩形表示
范围内的格子要被修改，红色部分就是 $p_{i,j}$ 为 $1$ 的部分。

称这个矩阵为阶梯矩阵，原来的状态称为 01 矩阵。

那么，所有的 01 矩阵都能唯一转化为一个阶梯矩阵，所以只需将原来的状态换成新的阶梯状态进行高斯消元即可。

而阶梯状态是不多的，只有 $\left(\genfrac{}{}{0ex}{}{n+m}{n}\right)$ 种，下面证明。

考虑每一行，看每行红色部分的格子数量，容易发现它们是有单调性的，设格子数量为 $i$ 的行数为 $x_i$，即方案就是求 $\sum _{i=0}^n{x}_i=m$ 的解的个数，这是组合数学的经典问题，易证。

而 $\left(\genfrac{}{}{0ex}{}{n+m}{n}\right)$ 最大也就 $\left(\genfrac{}{}{0ex}{}{10}{5}\right)=252$，高斯消元绰绰有余。

实现上，可以用 dfs 求出阶梯矩阵的状态和个数，01 矩阵转换成阶梯矩阵直接暴力枚举（时间充裕）每个点，若颜色不相同就直接对左上角修改。高斯消元要写模意义下的，我的实现直接用快速幂求逆元。

总的时间复杂度为 $O\left({\left(\genfrac{}{}{0ex}{}{n+m}{n}\right)}^3+\left(\genfrac{}{}{0ex}{}{n+m}{n}\right)n^3{m}^3\right)$

具体实现参照代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll mod=998244353;
const int N=260;
ll a[N][N],val[N];
int fr[N],nn,mm,n,m,cnt;
char s1[N][N],s2[N][N];
unordered_map<int,int> ma;
vector<int> v;
ll ksm(ll a,ll b)
{ll ans=1;while(b){if(b&1) ans=ans*a%mod;b>>=1;a=a*a%mod;}return ans;
}
int gauss()
{int r=1,c=1;for(;r<=nn&&c<=mm;r++,c++){int maxn=r;for(int i=r+1;i<=nn;i++) if(abs(a[maxn][c])<abs(a[i][c])) maxn=i;for(int j=1;j<=mm+1;j++){swap(a[maxn][j],a[r][j]);}if(abs(a[r][c])==0){r--;continue;}for(int i=1;i<=nn;i++){if(i==r) continue;ll g=(a[i][c]*ksm((a[r][c]%mod+mod)%mod,mod-2)%mod+mod)%mod;for(int j=1;j<=mm+1;j++)a[i][j]=(a[i][j]-a[r][j]*g%mod+2*mod)%mod;}}for(int i=r;i<=nn;i++){if(abs(a[i][i])==0&&abs(a[i][mm+1])>0){return -1;}}memset(fr,0x3f,sizeof(fr));for(int i=1;i<r;i++){int cnt=0,num=0;for(int j=1;j<=mm;j++) if(fr[j]&&abs(a[i][j])>0) cnt++,num=j;if(cnt==1) fr[num]=0,val[num]=(a[i][mm+1]*ksm((a[i][num]%mod+mod)%mod,mod-2)%mod+mod)%mod;}return 1;
}
int getid(int x,int y){return (x-1)*m+y;}
void dfs(int x,int k,int state)
{if(!x){ma[state]=++cnt;v.push_back(state);return;}for(int i=0;i<=k;i++) dfs(x-1,i,state|((1<<x*m)-1^(1<<x*m-i)-1));
}
int change(int id)
{int newid=(1<<n*m)-1;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){if((id>>getid(i,j)-1&1)!=(s2[i][j]=='B')){for(int ii=1;ii<=i;ii++){for(int jj=1;jj<=j;jj++){newid&=INT_MAX^(1<<getid(ii,jj)-1);}}}}}return newid;
}
int main()
{freopen("graffiti.in","r",stdin);freopen("graffiti.out","w",stdout);scanf("%d%d",&n,&m);for(int i=1;i<=n;i++) scanf("%s",s1[i]+1);for(int i=1;i<=n;i++) scanf("%s",s2[i]+1);int finish=0,start=0;for(int i=n;i>=1;i--){for(int j=m;j>=1;j--){finish=finish*2+(s2[i][j]=='B');start=start*2+(s1[i][j]=='B');}}dfs(n,m,0);int N=1<<n*m;nn=mm=v.size();for(int i=0;i<v.size();i++){int t=v[i];if(i==ma[change(finish)]-1){a[i+1][i+1]=1;continue;}int tt=0;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){if(t>>getid(i,j)-1&1) tt|=(s2[i][j]=='B')<<getid(i,j)-1;else tt|=(s2[i][j]=='W')<<getid(i,j)-1;}}a[ma[t]][ma[t]]+=2*n*m;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){int id=tt;for(int ii=1;ii<=i;ii++){for(int jj=1;jj<=j;jj++){id|=1<<(getid(ii,jj)-1);}}int newid=change(id);a[ma[t]][nn+1]+=i*j;a[ma[t]][ma[newid]]--;for(int ii=1;ii<=i;ii++){for(int jj=1;jj<=j;jj++){id^=1<<(getid(ii,jj)-1);}}newid=change(id);a[ma[t]][nn+1]+=i*j;a[ma[t]][ma[newid]]--;}}}int czn=gauss();printf("%lld\n",val[ma[change(start)]]);
}