Connecting Vertices
这个奇怪的限制（两条边不能有交点）让我们想到什么？
对于任何一种方案，不存在 \(x_0<x_1<y_0<y_1\)，其中连边 \((x_0,y_0),(x_1,y_1)\)。
也就是说，对于任何一段区间 \([i,j]\)，如果里面所有点全都连通：
要么 \(i,j\) 两点之间自己连了条边，此时，存在且仅存在一个 \(k\)，使得区间 \([i,k]\) 和 \([k+1,j]\) 间有且只有 \((i,j)\) 一条边；
要么可以找到一个点 \(k\)，使得区间 \([i,k-1]\) 与 \([k+1,j]\) 之间没有边，并且 \(k\) 与两个集合连通。
因此我们可以轻而易举写出：
\[(a_{i,j}=1):f[i,j]=\sum\limits_{k=i}^{j} f[i,k] \times f[k+1,j]
\]
\[f[i,j]=\sum\limits_{k=i+1}^{j-1} f[i,k] \times f[k,j]
\]
但是这样会出问题：
要么可以找到一个点 \(k\)，使得区间 \([i,k-1]\) 与 \([k+1,j]\) 之间没有边，并且 \(k\) 与两个集合连通。
并不表示这样的 \(k\) 唯一。例如，\((1,2)\rightarrow(2,3)\rightarrow(3,4)\) 中，2 是一个 \(k\)，3 也是一个 \(k\)，这同一种方案就被算了两边！
因此，我们可以只拿最左边那个 \(k\) 为准。即，\(i\) 与 \(k\) 直接连边的 \(k\) 才是好\(k\)。
我们新增维数：
设 \(f[i,j][0/1]\) 表示：区间 \(i,j\) 全部连通，并且 \(i,j\) 强制连边/强制不连边。
则有
\[(a_{i,j}=1):f[i,j][0]=\sum\limits_{k=i}^{j} (f[i,k][0]+f[i,k][1]) \times (f[k+1,j][0]+f[k+1,j][1])
\]
\[f[i,j]=\sum\limits_{k=i+1}^{j-1} f[i,k][0] \times (f[k,j][0]+f[k,j][1])
\]
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod=1e9+7;
const int N=550;
int n;
int g[N][N],f[N][N][2];
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) cin>>g[i][j];
for(int i=1;i<=n;i++) f[i][i][0]=1;
for(int l=2;l<=n;l++){
for(int i=1,j=i+l-1;j<=n;i++,j++){
if(g[i][j]){
for(int k=i;k<j;k++){
(f[i][j][0]+=(f[i][k][0]+f[i][k][1])*(f[k+1][j][0]+f[k+1][j][1])%mod)%=mod;
}
}
for(int k=i+1;k<j;k++){
if(g[i][k]){
(f[i][j][1]+=f[i][k][0]*(f[k][j][0]+f[k][j][1])%mod)%=mod;
}
}
}
}
cout<<(f[1][n][0]+f[1][n][1])%mod;
return 0;
}