首页 > 其他分享 >[AGC028D] Chords

[AGC028D] Chords

时间:2023-06-19 12:12:31浏览次数:38  
标签:605 连边 AGC028D Chords int 方案 线段 dp

[AGC028D] Chords

题意:给定一个圆, 圆上均等地放着 2n2n 个点, 已有 kk 对点之间连好了线段, 从中选择剩下 n−kn−k 对点随意连线段(每个点只连一条线段).

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

 

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

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

转化为区间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

 

标签:605,连边,AGC028D,Chords,int,方案,线段,dp
From: https://www.cnblogs.com/DongPD/p/17490823.html

相关文章