NOIP2023模拟10联测31 涂鸦

本文主要是介绍NOIP2023模拟10联测31 涂鸦，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目大意

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

$1\leq n,m\leq 5$

题解

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

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

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

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

在这里插入图片描述
其中橙色部分为 $p_{i,j}=1$ 的格子。

那么，总状态数为 $\binom{n+m}{n}$ 。我们可以用 $df s$ 求出所有可能的状态。

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

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

时间复杂度为 $O(\binom{n+m}{n}^3)$ ， $\binom{n+m}{n}$ 的最大值为 $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;
}