题解：CF888F Connecting Vertices

· · 题解

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}。

#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;
}