做做简单题放松身心。
考虑区间 dp，设 \(f_{i, j}\) 为只考虑 \([i, j]\) 的点的生成树个数。
转移枚举 \(i\) 往右连的最后一条边 \((i, k)\)，那么 \([k, j]\) 的点都不能往前连。
再设一个 \(g_{i, j}\) 为只考虑 \([i, j]\) 的点，并且连边 \((i, j)\) 的生成树个数。那么 \(f\) 有转移：
\[\forall k \in [i + 1, j], f_{i, j} \gets g_{i, k} \times f_{k, j}
\]
考虑如何求 \(g_{i, j}\)。因为是一棵树，所以连 \((i, j)\) 之前，\(i, j\) 必然不连通，并且此时 \([i, j]\) 形成 \(2\) 个连通块。枚举 \([i, k]\) 为 \(i\) 所属连通块，那么 \(g\) 有转移：
\[\forall k \in [i, j - 1], g_{i, j} \gets f_{i, k} \times f_{k + 1, j}
\]
做完了。时间复杂度 \(O(n^3)\)。
code
// Problem: F. Connecting Vertices
// Contest: Codeforces - Educational Codeforces Round 32
// URL: https://codeforces.com/problemset/problem/888/F
// Memory Limit: 256 MB
// Time Limit: 4000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mkp make_pair
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;
const int maxn = 510;
const ll mod = 1000000007;
ll n, a[maxn][maxn], f[maxn][maxn], g[maxn][maxn];
void solve() {
scanf("%lld", &n);
for (int i = 1; i <= n; ++i) {
f[i][i] = g[i][i] = 1;
for (int j = 1; j <= n; ++j) {
scanf("%lld", &a[i][j]);
}
}
for (int p = 2; p <= n; ++p) {
for (int i = 1, j = p; j <= n; ++i, ++j) {
if (a[i][j]) {
for (int k = i; k < j; ++k) {
g[i][j] = (g[i][j] + f[i][k] * f[k + 1][j] % mod) % mod;
}
}
for (int k = i + 1; k <= j; ++k) {
if (a[i][k]) {
f[i][j] = (f[i][j] + g[i][k] * f[k][j] % mod) % mod;
}
}
}
}
printf("%lld\n", f[1][n]);
}
int main() {
int T = 1;
// scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}