[AGC028D] Chords

题意：给定一个圆, 圆上均等地放着

两点联通当且仅当两点在同一条线段上或两点所属于的线段相交, 求所有连边方案中, 联通块的个数和.

对于圆/正多边形等问题，我们一般都要把他剖成线，对于这道题而言，如果两个区间相交而不包含，那么它们在原图上就是相交的。

我们不可能枚举每一种方案，故我们计算每一种连通块对答案的贡献。

转化为区间dp。dp（i,j）表示【i,j】内任意连边，使它们在一个连通块内，g（i）表示i个点随意连边的方案数，c（i,j）表示区间内没有被强制连边的方案数。

首先，我们可以通过打表找规律，提前处理出g。题目中说了每个点只能连一条边，故奇数无法连完，方案数为0.对于偶数，g（x）=g（x-2）*（x-1）。

c（i,j）很好处理。

假如我们先不考虑连边不合法的情况（指l的右端点不是r），dp【l】【r】=g（c（l,r））。

接下来，我们把不合法的情况减去。

而所有方案中，满足l,r在同一连通块的方案个数为

最后累加一下即为答案。

具体细节见代码

#include<cstdio>
#include<iostream>
using namespace std;
const int Mod=1e9+7;
int f[605][605];
int g[605],p[605],c[605];
int ans;
inline int h(int l,int r){return c[r]-c[l-1];}
void solve(int l,int r,int n){
    for(int i=l;i<=r;++i)
        if(p[i]&&p[i]<l||p[i]>r)return ;
    f[l][r]=g[h(l,r)];
    for(int i=l+1;i<r;++i)
        f[l][r]=(f[l][r]-1ll*f[l][i]*g[h(i+1,r)]%Mod+Mod)%Mod;
    ans+=1ll*f[l][r]*g[h(1,l-1)+h(r+1,n)]%Mod;
    ans%=Mod;
}
int main(){
    int n,m;cin>>n>>m;
    n<<=1;g[0]=1;
    for(int i=2;i<=n;i+=2)g[i]=1ll*g[i-2]*(i-1)%Mod;
    for(int i=1;i<=m;++i){
        int x,y;cin>>x>>y;
        p[x]=y,p[y]=x;
    }
    for(int i=1;i<=n;++i)c[i]=c[i-1]+(!p[i]);
    for(int i=1;i<=n;++i)
        for(int j=i+1;j<=n;j+=2)solve(i,j,n);
    cout<<ans<<'\n';
    return 0;
}

View Code

atcoder contest grand 028

526互联

[AGC028D] Chords

[AGC028D] Chords