Connecting Vertices CodeForces - 888F (图论,计数) - JavaScript

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

链接

大意: 给定邻接表表示两点是否可以连接, 要求将图连成树, 且边不相交的方案数

n范围比较小, 可以直接区间dp

$f[l][r]$表示答案, $g[l][r]$表示区间[l,r]全部连通且l,r间连边的方案

#include <iostream>
#include <algorithm>
#include <cstdio>
#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);
}