题解：P10042 [CCPC 2023 北京市赛] 三染色
Larunatrecy
·
·
题解
[CCPC 2023 北京市赛] 三染色
- 有一个高度矩阵 $h_{i,j}$，满足相邻的 $h$ 差的绝对值不超过 $1$。对于每一轮，如果某个点 $h_{i,j}$ 周围存在点的高度是 $h_{i,j}-1$，那么 $h_{i,j}=h_{i,j}-1$，否则不变，求出最终停止变化的时刻。
这个问题是简单的，因为最小值一定不变，并且每一轮最小值都会把周围的点也变为最小值，因此答案就是到 $(1,1)$ 曼哈顿距离最小的最小值点的距离。
考虑拓展一下，我们构造一个高度矩阵 $h_{i,j}$，使得除了满足上述条件，并且 $h_{i,j}\equiv a_{i,j}\pmod 3$，可以发现若能构造出来，那么 $h$ 与 $a$ 的变化就一模一样的，答案同上。
不妨令 $h_{1,1}=a_{1,1}$，然后归纳假设已经构造了 $h_{i-1,j},h_{i,j-1}$，因为 $|h_{i-1,j-1}-h_{i-1,j}|\leq 1,|h_{i-1,j-1}-h_{i,j-1}|\leq 1$ 都满足，所以通过简单的分类讨论可以发现当且仅当这个子矩阵形如这样时无法构造：
$$
\begin{pmatrix}
a & a\\
b & c
\end{pmatrix}
$$
当然，旋转或者整体加 $d$ 都也是不行的。
手玩一下可以发现，此时这个矩阵会不断自我迭代，因此一定不会稳定。故只要不存在这样的子矩形就一定是可以构造的，这就是第一问的答案，直接 $3^{2n}m$ 暴力状压 dp 即可通过。
对于第二问，我们需要维护最小高度，当前的高度，最小值位置，以及最后一列的状态，显然过不掉，考虑优化。
首先可以用轮廓线 dp 把状态变成 $3^n$，然后注意到我们不关心最小值具体是什么，只关心当前高度与最小高度的差，具体的，我们可以一开始就枚举 $h_{1,1}$ 比最小值高多少，并且实时记录差，强制过程中不经过差 $<0$ 的点，那么差 $=0$ 的点就是最小值点。
同时，我们其实也不关心最小值位置，只关心其曼哈顿距离，可以发现曼哈顿距离相等的点构成了一条斜线，我们只需要记录这一条线与当前列的交点即可，这个交点如果超出边界，以后也不可能更优了，直接计入答案即可，否则这个交点是 $O(n)$ 的。
综上，我们能在 $O(3^nn^2m^2)$ 的复杂度解决该问题。
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N = 55;
const int M = 4100;
int n,m;
int a[N][N];
const int mod = 998244353;
inline int add(int a,int b){return a+b>+mod?a+b-mod:a+b;}
inline void myplus(int &a,int b){a+=b;if(a>=mod)a-=mod;}
template <typename T>inline void read(T &x)
{
x=0;char c=getchar();bool f=0;
for(;c<'0'||c>'9';c=getchar())f|=(c=='-');
for(;c>='0'&&c<='9';c=getchar())x=((x<<1)+(x<<3)+(c^48));
x=(f?-x:x);
}
int f[2][M][N*2][8][3],g[2][M][N*2][3],pw[N];
int dp[N][M];
inline int get(int s,int i){return (s>>((i-1)<<1))&3;}
inline int gen(int c,int i){return c*(1<<((i-1)*2));}
inline int promote(int x,int y){if(y==x)return 0;if(y==(x+1)%3)return 1;return -1;}
int suan[M][N][3];
bool chk[3][3][3][3];
bool flag1[N][M],flag2[M][M];
bool chk2(int i,int s)
{
for(int j=1;j<=m;j++)
{
if(a[i][j]!=3&&get(s,j)!=a[i][j])return 0;
}
return 1;
}
bool chk3(int s,int t)
{
for(int j=1;j<=m-1;j++)
{
int c1=get(s,j),c2=get(s,j+1);
int c3=get(t,j),c4=get(t,j+1);
if(c1==c2&&c1!=c3&&c1!=c4&&c3!=c4)return 0;
if(c1==c3&&c1!=c2&&c1!=c4&&c2!=c4)return 0;
if(c2==c4&&c2!=c1&&c2!=c3&&c1!=c3)return 0;
if(c3==c4&&c3!=c1&&c3!=c2&&c1!=c2)return 0;
}
return 1;
}
vector<int> used;
void solve1()
{
for(int i=1;i<=n;i++)
for(int j:used)
flag1[i][j]=chk2(i,j);
for(int i:used)
{
for(int k:used)
flag2[i][k]=chk3(i,k);
}
for(int j:used)if(flag1[1][j])dp[1][j]=1;
for(int i=2;i<=n;i++)
for(int j:used)if(dp[i-1][j])
for(int k:used)if(flag1[i][k]&&flag2[j][k])
dp[i][k]=add(dp[i][k],dp[i-1][j]);
int res=0;
for(int j:used)res=(res+dp[n][j])%mod;
cout<<res<<' ';
}
int main()
{
read(m);read(n);
for(int j=1;j<=m;j++)
for(int i=1;i<=n;i++)
read(a[i][j]);
pw[0]=1;
int cur=0;
for(int i=1;i<=m;i++)pw[i]=pw[i-1]*4;
int t=1;
for(int i=1;i<=m;i++)t=t*3;
for(int u=0;u<t;u++)
{
int s=0,x=u;
for(int i=1;i<=m;i++)
{
int c=x%3;
x/=3;
s+=gen(c,i);
}
used.push_back(s);
}
solve1();
for(int s:used)
{
int i=1;
int mn=0,d=0,p=1;bool flag=1;
for(int j=1;j<=m;j++)
{
if(a[i][j]!=3&&get(s,j)!=a[i][j])
{
flag=0;
break;
}
if(j>1)
{
d=d+promote(get(s,j-1),get(s,j));
if(d<mn)
{
mn=d;
p=j;
}
}
}
if(flag)
for(int v=-(n+m);v<=mn;v++)
{
if(v==mn)f[cur][s][0-v][p][0]++;
else g[cur][s][0-v][0]++;
}
}
for(int s:used)
{
for(int i=2;i<=m;i++)
for(int c=0;c<=2;c++)
{
int d=0;
for(int j=1;j<i-1;j++)d+=promote(get(s,j),get(s,j+1));
d+=promote(get(s,i-1),c);
suan[s][i][c]=d;
}
}
for(int c1=0;c1<=2;c1++)for(int c2=0;c2<=2;c2++)
for(int c3=0;c3<=2;c3++)for(int c4=0;c4<=2;c4++)
{
if(c1==c2&&c1!=c3&&c1!=c4&&c3!=c4)continue;
if(c1==c3&&c1!=c2&&c1!=c4&&c2!=c4)continue;
if(c2==c4&&c2!=c1&&c2!=c3&&c1!=c3)continue;
if(c3==c4&&c3!=c1&&c3!=c2&&c1!=c2)continue;
chk[c1][c2][c3][c4]=1;
}
int all=0;
for(int i=2;i<=n;i++)
{
if(i)
{
int j=1;
int nxt=(cur^1);
for(int s:used)
for(int d=0;d<=n+m;d++)
{
int w=0;
for(int sp=0;sp<=2;sp++)w=add(w,g[cur][s][d][sp]),g[cur][s][d][sp]=0;
if(!w)continue;
for(int c=0;c<=2;c++)
{
if(a[i][j]!=3&&a[i][j]!=c)continue;
all++;
int ns=s-gen(get(s,j),j)+gen(c,j),nsp=get(s,j),nv=d+promote(get(s,j),c);
if(nv>0)//keep
{
myplus(g[nxt][ns][nv][nsp],w);
}
else if(nv==0)//update
{
myplus(f[nxt][ns][nv][j][nsp],w);
}
}
}
for(int s:used)
for(int d=0;d<=n+m;d++)
for(int r=0;r<=m;r++)
{
int w=0;
for(int sp=0;sp<=2;sp++)w=add(w,f[cur][s][d][r][sp]),f[cur][s][d][r][sp]=0;
if(!w)continue;
for(int c=0;c<=2;c++)
{
if(a[i][j]!=3&&a[i][j]!=c)continue;
all++;
int ns=s-gen(get(s,j),j)+gen(c,j),nv=d+promote(get(s,j),c),nr=max(0,r-1),nsp=get(s,j);
if(nv>0||(nv==0&&nr<=j))//keep
{
if(r==1&&nr==0)
myplus(f[nxt][ns][nv][nr][nsp],1ll*w*(i-1+r-2)%mod);
else
myplus(f[nxt][ns][nv][nr][nsp],w);
}
else if(nv==0)//update
{
myplus(f[nxt][ns][nv][j][nsp],w);
}
}
}
cur=nxt;
}
for(int j=2;j<=m;j++)
{
int nxt=(cur^1);
for(int s:used)
for(int d=0;d<=n+m;d++)
for(int sp=0;sp<=2;sp++)
if(g[cur][s][d][sp])
{
for(int c=0;c<=2;c++)
{
if(a[i][j]!=3&&a[i][j]!=c)continue;
if(!chk[sp][get(s,j)][get(s,j-1)][c])continue;
if(d+suan[s][j][c]<0)continue;
all++;
int ns=s-gen(get(s,j),j)+gen(c,j),nsp=get(s,j),nv=d+suan[s][j][c];
if(nv>0)//keep
{
myplus(g[nxt][ns][d][nsp],g[cur][s][d][sp]);
}
else if(nv==0)//update
{
myplus(f[nxt][ns][d][j][nsp],g[cur][s][d][sp]);
}
}
g[cur][s][d][sp]=0;
}
for(int s:used)
for(int d=0;d<=n+m;d++)
for(int r=0;r<=m;r++)
for(int sp=0;sp<=2;sp++)
if(f[cur][s][d][r][sp])
{
for(int c=0;c<=2;c++)
{
if(a[i][j]!=3&&a[i][j]!=c)continue;
if(!chk[sp][get(s,j)][get(s,j-1)][c])continue;
if(d+suan[s][j][c]<0)continue;
all++;
int ns=s-gen(get(s,j),j)+gen(c,j),nr=r,nsp=get(s,j),nv=d+suan[s][j][c];
if(nv>0||(nv==0&&nr<=j))//keep
{
if(r==1&&nr==0)
myplus(f[nxt][ns][d][nr][nsp],1ll*f[cur][s][d][r][sp]*(i-1+r-2)%mod);
else
myplus(f[nxt][ns][d][nr][nsp],f[cur][s][d][r][sp]);
}
else if(nv==0)//update
{
myplus(f[nxt][ns][d][j][nsp],f[cur][s][d][r][sp]);
}
}
f[cur][s][d][r][sp]=0;
}
cur=nxt;
}
}
int ans=0;
for(int s:used)
for(int d=0;d<=n+m;d++)
for(int sp=0;sp<=2;sp++)
{
myplus(ans,f[cur][s][d][0][sp]);
for(int r=1;r<=m;r++)myplus(ans,1ll*f[cur][s][d][r][sp]*(n+r-2)%mod);
}
cout<<ans;
return 0;
}
```