[DP记录]AT4438 [AGC028D] Chords
command_block
2021-10-10 17:38:43
**题意** ： 给出圆上均匀分布的 $2n$ 个点，要求连接 $n$ 条弦，使得每个点只连接一条弦。
已给出 $k$ 条弦，问在所有连边方案中，弦形成的联通块数目的和。
答案对 $10^9+7$ 取模。
$n\leq 300$ ，时限$\texttt{2s}$。
------------
将圆转化为 $[1,2n]$ 的序列。可以发现两条弦 $[l_1,r_1],[l_2,r_2]$ 相交当且仅当两区间相交但不包含（部分相交）。
对于每个联通块，将其拍扁形成覆盖区间 $[l,r]$ 。某组方案内，各个联通块的覆盖区间都不会部分相交。
考虑每个覆盖区间 $[l,r]$ 的贡献系数。
记 $t_u$ 表示点 $u$ 连出弦的另一个端点。
$[l,r]$ 成为覆盖区间，当且仅当 $l,r$ 在同一个联通块内，且对于 $k\in [l,r]$ ，$t_k\in[l,r]$。
考虑如何计算方案数。
记 $g[n]$ 为 $n$ 个点内部随意匹配的方案数， $h_{l,r}$ 为区间 $[l,r]$ 内（初始时）没有弦相连的点数，$f[l,r]$ 表示只考虑点 $l\sim r$ 的方案数。
则 $[l,r]$ 成为覆盖区间的方案数为 $f[l,r]\times g[h_{1,l-1}+h_{r+1,2n}]$ 。
显然有 $g[n]=[2|n]\prod\limits_{i=1}^{n/2}(n-2i+1)$ 。
对于 $f[l,r]$ ，考虑将 $l\sim r$ 内的点随便连，然后减去 $[l,r]$ 不连通的情况。即：
$$f[l,r]=g[h_{l,r}]-\sum\limits_{k=l+1}^{r-1}f[l,k]g[h_{k+1,r}]$$
和式中枚举的是第一个联通前缀，可以做到不重不漏。（经典技巧）
复杂度为 $O(n^3)$。
```cpp
#include<algorithm>
#include<cstdio>
#define MaxN 605
using namespace std;
const int mod=1000000007;
int n,k,c[MaxN],s[MaxN],g[MaxN],f[MaxN][MaxN];
#define h(l,r) (c[r]-c[l-1])
int main()
{
scanf("%d%d",&n,&k);
for (int i=1;i<=n+n;i++)c[i]=1;
for (int i=1,u,v;i<=k;i++){
scanf("%d%d",&u,&v);
int x=rand()<<15^rand();
s[u]=s[v]=x;c[u]=c[v]=0;
}
for (int i=1;i<=n+n;i++)
{s[i]^=s[i-1];c[i]+=c[i-1];}
for (int i=0;i<=n+n;i+=2){
g[i]=1;
for (int j=1;j<=i/2;j++)
g[i]=1ll*g[i]*(i-2*j+1)%mod;
}
int ans=0;
for (int d=1;d<n+n;d++)
for (int l=1;l+d<=n+n;l++){
int r=l+d;
if (s[r]^s[l-1])continue;
f[l][r]=g[h(l,r)];
for (int k=l+1;k<=r-1;k++)
f[l][r]=(f[l][r]-1ll*f[l][k]*g[h(k+1,r)])%mod;
ans=(ans+1ll*f[l][r]*g[h(1,l-1)+h(r+1,2*n)])%mod;
}
printf("%d",(ans+mod)%mod);
return 0;
}
```