-
分析
手玩样例发现连一条边实际上是将一个多边形分割成两个部分，而且不能在这两个部分直接连边，发现这两个部分是完全独立的，于是考虑区间 DP。
设状态 \(f_{l,r}\) 表示将 \([l,r]\) 区间连成树的方法数量。
那么存在两种转移，一种是 \(l,r\) 间不直接连边，这样中间的点都需要连边，一种是 \(l, r\) 间直接连边，这样中间的点有一对就不需要连通了。发现第一种转移如果左区间的 \(l\) 没直接连通到 \(r\)，那么在划给左区间计算一次后，又会将 \(r\) 划给了右区间再次被计算，所以我们要将 \(l\) 和 \(r\) 是否连通计入状态，\(f_{l,r,0}\) 表示不连通，\(f_{l,r,1}\) 表示连通。
那么转移方程就是 \(f_{l,r,0}=\sum_{k=l+1}^{r-1}f_{l,k,0}(f_{k,r,0}+f_{k,r,1})\)，\(f_{l,r,0}=\sum_{k=l}^{r-1}(f_{l,k,0}+f_{l,k,1})(f_{k+1,r,0}+f_{k+1,r,1})\)。
最后的答案就是 \(f_{1,n,0}+f_{1,n,1}\)。 -
代码
#include <iostream>
#define int long long
using namespace std;
constexpr int MAXN(507);
constexpr int mod(1000000007);
int vis[MAXN][MAXN][2], f[MAXN][MAXN][2], g[MAXN][MAXN];
int n;
inline void read(int &temp) { cin >> temp; }
int dfs(int l, int r, int sy) {
if (vis[l][r][sy]) return f[l][r][sy];
vis[l][r][sy] = 1;
if (l == r) return f[l][r][sy] = sy;
if (sy && !g[l][r]) return f[l][r][sy] = 0;
int res(0);
if (sy)
for (int k(l); k < r; ++k) res = (res + (dfs(l, k, 1) + dfs(l, k, 0)) % mod * (dfs(k + 1, r, 1) + dfs(k + 1, r, 0))) % mod;
if (!sy)
for (int k(l + 1); k < r; ++k) res = (res + dfs(l, k, 1) * (dfs(k, r, 0) + dfs(k, r, 1)) % mod) % mod;
return f[l][r][sy] = res;
}
signed main() {
ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
read(n);
for (int i(1); i <= n; ++i)
for (int j(1); j <= n; ++j) read(g[i][j]);
cout << (dfs(1, n, 0) + dfs(1, n, 1)) % mod << endl;
return 0;
}