题解：AT_abc379_g [ABC379G] Count Grid 3-coloring
Mr_Terminator
2024-11-19 12:23:18
首先，这是计数题，而且很明显是个状态压缩。
其次，我们的状态数量好像是 $3^{14}$，看起来也很不可做。
但是继续想想：题目中的限制条件就是相邻两个格子颜色不得相同，那么状态数量实际上是 $3\times 2^{13}$。你不相信这个状态数？首先选择一行第一个格子，共 $3$ 个颜色，其次依次往后选择格子，每次有 $2$ 个可选颜色。这样状态数量就可以计算出来是这么多了。
最后——我们状态数量虽然不多，但是从一行的状态到下一行的状态转移数量好像是 $9\times 4^{13}$ 啊，这更不可做了。
不过，相邻两行之间对应的位置也不一样。我们计算一下两行之间相邻格子不同颜色的方案数——任意选择两行的第一个格子（共 $6$ 种方案），然后依次地同时选择两行的第 $2$ 到 $14$ 个格子（每次有 $3$ 种方案）。这样，转移数是 $6\times 3^{13}=2\times 3^{14}$ 个。
我们只要使用两次 $\text{dfs}$，预处理出所有状态数，并使用 $\text{vector}$ 存储两个状态间的所有转移。在扫到每一行的时候，查看这个状态是否匹配了该行所有已给的格子颜色，接着转移即可。时间复杂度 $O(\max(H,W)3^{\min(H,W)}+HW2^{\min(H,W)})$，稳稳地过。
实现细节以及套路：
- $\text{dfs}$ 前开一个大小为 $3\times 2^{13}$ 的用于**离散化**的数组，将数值值域大小为 $3^{14}$ 的状态存储在对应编号里，这样容易在状态压缩 $\text{dp}$ 时找到 $14$ 个格子的颜色用于检验。
- 不要在 $\text{dp}$ 过程中检查两个状态是否存在相同颜色的位置。如果你不想死，请预处理所有转移。
代码：
```cpp
#include<bits/stdc++.h>
using namespace std;
int h,w,rawgrid[205][205],grid[205][15],lsh[4782969],Nlsh[25005],mi3[15],dp[205][50005],pt1,CnT,ans;
const int modp=998244353;vector<int>canbe[25005];bool enable[205][25005];
void dfs(int now,int cur,int lst){
if(now==w){
pt1++;lsh[cur]=pt1;Nlsh[pt1]=cur;return;
}
for(int o=0;o<3;o++){
if(o==lst)continue;
dfs(now+1,cur+o*mi3[now],o);
}
}
void dfs2(int now,int ocur,int cur,int lst1,int lst2){
if(now==w){
canbe[lsh[ocur]].push_back(lsh[cur]);return;
}
for(int o=0;o<3;o++){
if(o==lst1)continue;
for(int oo=0;oo<3;oo++){
if(oo==lst2)continue;
if(o==oo)continue;
dfs2(now+1,ocur+o*mi3[now],cur+oo*mi3[now],o,oo);
}
}
}
bool bean(int xx,int rw){
for(int i=1;i<=w;i++){
if(grid[rw][i]!=0&&xx%3!=grid[rw][i]-1)return 0;
xx/=3;
}
return 1;
}
int main(){
cin>>h>>w;mi3[0]=1;
for(int i=1;i<=14;i++)mi3[i]=mi3[i-1]*3;
for(int i=1;i<=h;i++){
string s;cin>>s;
for(int j=1;j<=w;j++){
if(s[j-1]!='?')rawgrid[i][j]=s[j-1]-'0';
}
}
if(h<w){
for(int i=1;i<=h;i++){
for(int j=1;j<=w;j++){
grid[j][i]=rawgrid[i][j];
}
}
swap(h,w);
}
else{
for(int i=1;i<=h;i++){
for(int j=1;j<=w;j++){
grid[i][j]=rawgrid[i][j];
}
}
}
dfs(0,0,-1);dfs2(0,0,0,-1,-1);//cout<<pt1<<' '<<CnT;
for(int i=1;i<=h;i++){
for(int zt=1;zt<=pt1;zt++){
enable[i][zt]=bean(Nlsh[zt],i);
}
}
for(int zt=1;zt<=pt1;zt++){
if(enable[1][zt])dp[1][zt]=1;
}
for(int i=1;i<h;i++){
for(int zt=1;zt<=pt1;zt++){
if(!enable[i][zt])continue;
for(auto zt2:canbe[zt]){
if(enable[i+1][zt2])dp[i+1][zt2]=(dp[i+1][zt2]+dp[i][zt])%modp;
}
}
}
for(int i=1;i<=pt1;i++){
ans=(ans+dp[h][i])%modp;
}
cout<<ans;
return 0;
}
```