状压 dp，2 hd 4 me/ng。
题意
开始你有一个全 \(0\) 矩阵，你可以随意执行如下操作：
- 选择任意一行，将其从最左端开始的连续一段染成 \(1\)。
- 选择任意一列，将其从最上端开始的连续一段染成 \(1\)。
如果一个矩阵可以由此得到，那么这个矩阵被称为好的。
现在你有一个 01? 矩阵 \(a\)，你需要将所有 ? 替换为 0 或 1，问得到的矩阵中有多少个是好的。答案对 \(998244353\) 取模。
\(1\le n,m\le 18\)。
思路
可以发现一个矩阵是否合法取决于对每个格子而言，其上方或左方是否有一方仍是全 \(1\) 段。
于是考虑设 \(f_{(i,j),s,k=0/1}\) 表示现在处理完了 \((i,j)\)，列状态为 \(s\)（列状态指目前 \(m\) 列里每一列是否仍为全 \(1\) 段），行状态为 \(k\)（即当前行是否仍为全 \(1\) 段）。
初始状态为 \(f_{(1,0),\text{full},1}=1\)，即啥都没填的情况。
对当前状态 \(f_{(i,j),s,k}\)，我们分类讨论：
\(j<m\)（格子不在行末）
那么下一个格子即为 \((i,j+1)\)，我们继续分类讨论：
- \(a_{i,j+1}=0\)：那么第 \(j+1\) 列的列状态则变成 \(0\)，第 \(i\) 行的行状态变为 \(0\)，即 \(f_{(i,j),s,k}\to f_{(i,j+1),s_{j+1}\gets 0,0}\)。
- \(a_{i,j+1}=1\)：要求当前行状态与第 \(j+1\) 列的列状态不能全为 \(0\)，转移方程为 \(f_{(i,j),s,k}\to f_{(i,j+1),s,k}\)。
- \(a_{i,j+1}=\text{?}\)：综合上面两种情况即可。
\(j=m\)（格子在行末）
那么下一个格子即为 \((i+1,1)\)，继续分类讨论/oh：
- \(a_{i+1,1}=0\)：那么第 \(1\) 列的列状态变成 \(0\)，且第 \(i+1\) 行的行状态变成 \(0\)，即 \(f_{(i,m),s,k}\to f_{(i+1,1),s_1\gets 0,0}\)。
- \(a_{i+1,1}=1\)：无要求，因为这就是第 \(i+1\) 行的顶头格子，直接 \(f_{(i,m),s,k}\to f_{(i+1,1),s,1}\)。
- \(a_{i+1,1}=\text{?}\)：综合上面两种情况即可。
最终答案即为 \(\displaystyle\sum_{i}\sum_{j}f_{(n,m),i,j}\)。
标签：状态,le,格子,题解,ABC295Ex,矩阵,text From： https://www.cnblogs.com/bykem/p/17259641.html