[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