NOIP2023模拟10联测31 涂鸦

题目大意

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

$1\le n,m\le 5$

题解

看到$n$和$m$都比较小，我们考虑用状压$DP$。设$f_s$表示当前墙面的状态为$s$时要到最终状态的期望代价，可以列出$2^{nm}$个方程，用高斯消元解方程即可。

这样做的时间复杂度为$O(2^{3nm})$，我们考虑优化。

我们考虑减少状态的数量。我们发现，如果一个位置的右下角的某个位置与最终状态不同，则这个位置一定会被修改，那这个位置当前的值就不重要了。

设$p_{i,j}$表示$(i,j)$右下角的位置是否已经全部变得和终止状态一样，可以发现$p_{i,j}$为$1$的状态一定在右下角呈阶梯状的。举个例子：

其中橙色部分为$p_{i,j}=1$的格子。

那么，总状态数为$\left(\genfrac{}{}{0ex}{}{n+m}{n}\right)$。我们可以用$dfs$求出所有可能的状态。

对于每个状态，我们考虑它能到达哪些状态。我们将每种状态中$p_{i,j}=1$的格子设为与终止状态相同，$p_{i,j}=0$的格子设为与终止状态相反。然后将左上角的一个矩形全部变为黑色或白色，再判断改变颜色后的状态是什么状态。

用上述方法求出转移方程，再用高斯消元求解即可。

时间复杂度为$O({\left(\genfrac{}{}{0ex}{}{n+m}{n}\right)}^3)$，$\left(\genfrac{}{}{0ex}{}{n+m}{n}\right)$的最大值为$252$，是可以过的。

code

#include<bits/stdc++.h>
using namespace std;
const long long mod=998244353;
int n,m,S,bg=0,ed=0,sum=0,tot=0,w[10][10];
long long ans=0,a[305][305];
char s[10][10],t[10][10];
array<int,5>v;
map<array<int,5>,int>mp;
void init(){S=(1<<n*m)-1;for(int i=0;i<n;i++){for(int j=0;j<m;j++){for(int x=0;x<=i;x++){for(int y=0;y<=j;y++){w[i][j]|=1<<(x*m+y);}}}}for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){sum+=2*i*j;}}
}
void dfs(int t,int now){if(t==n){mp[v]=++tot;return;}for(int i=now;i<=m;i++){v[t]=i;dfs(t+1,i);}
}
int gtid(int s){array<int,5>b;for(int i=0;i<5;i++) b[i]=0;for(int i=0;i<n;i++){b[i]=m;for(int j=0;j<m;j++){int wt=(s>>(i*m+j))&1;if(wt==(t[i][j]=='W')) b[i]=m-j-1;}}for(int i=n-2;i>=0;i--) b[i]=min(b[i],b[i+1]);return mp[b];
}
long long mi(long long t,long long v){if(!v) return 1;long long re=mi(t,v/2);re=re*re%mod;if(v&1) re=re*t%mod;return re;
}
void gauss(){for(int i=1;i<=tot;i++){for(int j=i;j<=tot;j++){if(a[j][i]){swap(a[j],a[i]);break;}}for(int j=1;j<=tot;j++){if(i==j) continue;long long dv=(mod-1)*a[j][i]%mod*mi(a[i][i],mod-2)%mod;for(int k=1;k<=tot+1;k++) a[j][k]=(a[j][k]+dv*a[i][k])%mod;}}
}
int main()
{
//	freopen("graffiti.in","r",stdin);
//	freopen("graffiti.out","w",stdout);scanf("%d%d",&n,&m);init();for(int i=0;i<n;i++) scanf("%s",s[i]);for(int i=0;i<n;i++) scanf("%s",t[i]);for(int i=0;i<n;i++){for(int j=0;j<m;j++){bg|=(s[i][j]=='B')<<(i*m+j);ed|=(t[i][j]=='B')<<(i*m+j);}}dfs(0,0);for(auto p:mp){int s=0,id=p.second;for(int i=0;i<n;i++){for(int j=0;j<m;j++){if(j<m-p.first[i])s|=(t[i][j]=='W')<<(i*m+j);elses|=(t[i][j]=='B')<<(i*m+j);}}a[id][id]=2*n*m;if(s==ed) continue;a[id][tot+1]=sum;for(int i=0;i<n;i++){for(int j=0;j<m;j++){int tmp=gtid(s|w[i][j]);a[id][tmp]=(a[id][tmp]-1+mod)%mod;tmp=gtid(s&(S^w[i][j]));a[id][tmp]=(a[id][tmp]-1+mod)%mod;}}}gauss();int tmp=gtid(bg);ans=a[tmp][tot+1]*mi(a[tmp][tmp],mod-2)%mod;printf("%lld",ans);return 0;
}