先给出一些定义。

【定义：可分离序列】

定义一个序列 $x_1,x_2,\cdots,x_n$ 是可分离的，当且仅当满足下面条件之一：

• $n=1$；
• 将 $x$ 升序排序后，满足 $x_{i+1}=x_i+1$。且存在 $1 \le k < n$ 使得 $x_1,x_2,\cdots,x_k$ 和 $x_{k+1},x_{k+2},\cdots,x_n$ 均为可分离序列。

若 $x_1 \sim x_k$ 比 $x_{k+1} \sim x_n$ 大，则称其为 A 型可分离序列，否则称其为 B 型可分离序列。

手玩一下，可以发现当 $p$ 是可分离序列，且 $B_{i,p_i}=1$ 时 $A$ 是好矩阵。

显然 $A$ 矩阵每行每列至少 $1$ 个 $1$，否则可能存在一些行/列填不满。

又因为 $A$ 矩阵至多 $n$ 个 $1$，所以 $A$ 矩阵每行每列恰好一个 $1$，这样 $A$ 可以用一个 $1 \sim n$ 的排列 $p_1,p_2,\cdots,p_n$ 表示。

具体地，$n=1$ 时一定能全变成 $1$，否则原来的矩阵一定可以划分为 $4$ 个小矩阵，且一定是下面两种情况之一（对应 A/B 型可分离序列）。

其中 $2$ 个白色小矩阵初始时全是 $0$，$2$ 个红色小矩阵一定都是方阵，且都是好的。

此时就可以区间 DP 了，设 $f_{x,y,z}$ 为：考虑 $p_x \sim p_{x+z-1}$，这一部分值域为 $y \sim y+z-1$ 时，$p_x \sim p_{x+z-1}$ 成为可分离序列的方案数。转移时枚举分割点 $t$，分 A 型和 B 型两种情况转移。

但是这样会算重。具体地，当 $p_x \sim p_{z_1},p_{z_1+1} \sim p_{z_2},p_{z_2+1} \sim p_y$ 均为可分离序列时，分割点可以是 $z_1$ 或 $z_2$，就重复了。

此时可以设 $g_{x,y,z}$ 为 A 型的方案数，$h_{x,y,z}$ 为 B 型的方案数，强制 A 型由若干个 B 型拼成，B 型由若干个 A 型拼成。

这样就不会算重了，时间复杂度 $O(n^4)$，但是常数极小，可以通过。

#include<bits/stdc++.h>
using namespace std;
const int N=160,p=998244353;
int n,b[N][N],f[N][N][N],g[N][N][N],h[N][N][N];
int main(){
	cin>>n;
	for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) cin>>b[i][j];
	for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) f[1][i][j]=g[1][i][j]=h[1][i][j]=b[i][j];
	for(int l=2;l<=n;l++) for(int i=1;i+l-1<=n;i++) for(int j=1;j+l-1<=n;j++){
		for(int k=1;k<l;k++) g[l][i][j]=(g[l][i][j]+1ll*h[k][i][j]*f[l-k][i+k][j+k]%p)%p;
		for(int k=1;k<l;k++) h[l][i][j]=(h[l][i][j]+1ll*g[k][i][j+l-k]*f[l-k][i+k][j]%p)%p;
		f[l][i][j]=(g[l][i][j]+h[l][i][j])%p;
	}
	return cout<<f[n][1][1]<<'\n',0;
}