大意: 给定邻接表表示两点是否可以连接, 要求将图连成树, 且边不相交的方案数
n范围比较小, 可以直接区间dp
$f[l][r]$表示答案, $g[l][r]$表示区间[l,r]全部连通且l,r间连边的方案
#include#include #include #define PER(i,a,n) for(int i=n;i>=a;--i)#define REP(i,a,n) for(int i=a;i<=n;++i)using namespace std;typedef long long ll;const int P = 1e9+7, N = 555;struct _ {int f=-1,g;}dp[N][N];int a[N][N], n;_ dfs(int l, int r) { _ &ans = dp[l][r]; if (~ans.f) return ans; ans.f=0; for (int x=l; ; x=(x+1)%n) { if (x!=l) (ans.f+=(ll)dfs(l,x).g*dfs(x,r).f%P)%=P; if (x==r) break; if (a[l][r]) (ans.g+=(ll)dfs(l,x).f*dfs((x+1)%n,r).f%P)%=P; } return ans;}int main() { scanf("%d", &n); REP(i,0,n-1)REP(j,0,n-1) scanf("%d", &a[i][j]),dp[i][i].f=1; printf("%d\n", dfs(0,n-1).f);}