Solution

显然要断环成链。我们要计算出

f_{l,r}

表示

l

和

r

联通的方案数。

如果

l

和

r

之间需要有连边，则将它删掉之后，区间

[l,r]

中的点恰好分为两个连通块；如果没有连边，我们可以找到最大的

u

使得

u

和

r

有连边，这样拆分成

[l,u]

联通与

[u,r]

联通。

我们发现，还是要记录

l

和

r

有连边的方案数，设为

g_{l,r}

。

因此转移就是：

g_{l,r} = a_{l,r} \sum_{t=l}^{r-1} f_{l,t}f_{t+1,r}

以及

f_{l,r} = g_{l,r} + \sum_{u=l+1}^{r-1} f_{l,u}g_{u,r}

答案就是

f_{1,n}

。

CPP

#include<bits/stdc++.h>
#define int long long
#define ffor(i,a,b) for(int i=(a);i<=(b);i++)
#define roff(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
const int MAXN=500+10,MOD=1e9+7;
int n,a[MAXN][MAXN],f[MAXN][MAXN],g[MAXN][MAXN];
signed main() {
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>n;
	ffor(i,1,n) ffor(j,1,n) cin>>a[i][j];
	ffor(i,1,n) f[i][i]=1;
	ffor(len,2,n) for(int l=1,r=len;r<=n;l++,r++) {
		if(a[l][r]) ffor(t,l,r-1) g[l][r]=(g[l][r]+f[l][t]*f[t+1][r])%MOD;
		f[l][r]=g[l][r];
		ffor(u,l+1,r-1) f[l][r]=(f[l][r]+f[l][u]*g[u][r])%MOD;
	}
	cout<<f[1][n];
	return 0;
}

题解：CF888F Connecting Vertices

文章操作

Solution

相关推荐

评论

题解：CF888F Connecting Vertices