NOIP2023模拟10联测31 涂鸦

联测31 涂鸦"/>

NOIP2023模拟10联测31 涂鸦

题目大意

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

1 ≤ n , m ≤ 5 1\leq n,m\leq 5 1≤n,m≤5

题解

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

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

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

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

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

那么，总状态数为 ( n + m n ) \binom{n+m}{n} (nn+m​)。我们可以用 d f s dfs dfs求出所有可能的状态。

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

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

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