Statement

有一个正 nn 边形，顶点顺时针编号为 1∼n1\sim n。问用 n−1n-1 条边连接这 nn 个顶点，使它们连成一棵树，有多少种方法。

连边时有以下限制：

  • 给出一个 n×nn\times n 的 01 矩阵 AA，Ai,j=1A_{i,j}=1 表示顶点 ii 和顶点 jj 可以直接相连，而 Ai,j=0A_{i,j}=0 时则不能。保证 Ai,i=0A_{i,i}=0，Ai,j=Aj,iA_{i,j}=A_{j,i}。
  • 两条线段不能在顶点之外的地方相交，如不能同时连 (1,3)(1,3) 和 (2,4)(2,4)。

数据范围：n≤500n\le500。

Solution

计数 DP 的一般套路是要构造一个“不可划分的整体”。—— sol1

考虑区间 DP，因为如果 ii 和 jj 有边，则 i+1∼j−1i+1\sim j-1 中不可能有连出去的边。

记 f(i,j)f(i,j) 表示 ii 和 jj 有边时，i∼ji\sim j 连边情况的方案数。发现转移复杂度较高，因此再记 g(i,j)g(i,j) 表示 ii 和 jj 不一定右边时 i∼ji\sim j 连边情况的方案数。有转移：

f(i,j)=Ai,j⋅∑x=ij−1g(i,x)⋅g(x+1,j)g(i,j)=f(i,j)+∑x=i+1j−1g(i,x)⋅f(x,j)\begin{aligned} f(i,j)&=A_{i,j}\cdot\sum_{x=i}^{j-1}g(i,x)\cdot g(x+1,j)\\ g(i,j)&=f(i,j)+\sum_{x=i+1}^{j-1}g(i,x)\cdot f(x,j) \end{aligned}

边界：f(i,i)=g(i,i)=1f(i,i)=g(i,i)=1，f(i,i)=f(i,i+1)=ai,i+1f(i,i)=f(i,i+1)=a_{i,i+1}。

目标解：g(1,n)g(1,n)。

时间复杂度 O(n3)O(n^3)。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <bits/stdc++.h>
typedef long long LL; const int N = 507, mod = 1e9 + 7;
int n, a[N][N]; LL f[N][N], g[N][N];
int main() {
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++)
        scanf("%d", a[i] + j);
    for(int i = 1; i <= n; i++)
        f[i][i] = g[i][i] = 1, f[i][i + 1] = g[i][i + 1] = a[i][i + 1];
    for(int i = n; i; i--) for(int j = i + 2; j <= n; j++) {
        for(int x = i; x < j; x++) {
            if(a[i][j]) f[i][j] = (f[i][j] + g[i][x] * g[x + 1][j]) % mod;
            if(x > i) g[i][j] = (g[i][j] + g[i][x] * f[x][j]) % mod;
        }
        g[i][j] = (g[i][j] + f[i][j]) % mod;
    }
    return printf("%lld\n", g[1][n]), 0;
}