Problem

Description

给定一个圆，圆上均等地放着 \(2n\) 个点，已有 \(k\) 对点之间连好了边，从中选择剩下 \(n-k\) 对点随意连边。

求所有连边方案中，联通块的个数和。

联通块的定义为：若两对点之间的线段相交，则在一个联通块内。

Range

\(1\le k\le n\le300\)

Algorithm

\(DP\)

Mentality

很奇妙的题目。

我们转换成考虑每对点对的贡献。

设 \(f_{i,j}\) 表示 \(i,j\) 相连，且 \(i,j\) 之间的所有点连的边都不与边 \(i,j\) 相交的方案数。

则可以考虑用 \(i,j\) 之间的点随便连的方案数减去 \(i,j\) 不联通的方案数。

考虑枚举一个 \(i<k<j\) ，钦定 \(i,k\) 相连，然后 \(k+1,j\) 之间的点随便连即可。

那么设 \(g_i\) 为 \(i\) 个点之间随便连的方案数，则 \(i\) 必须为偶数。

设 \(F(i,j)\) 为 \(i,j\) 之间没有被钦定的点数。

则有：

\[ f_{i,j}=g_{F(i,j)} - \sum_{k=i+1}^{j-1} f_{i,k}*g_{F(k+1,j)} \]

那么最后的答案自然为每个点对构成的联通块的贡献：

\[ ans=\sum f_{i,j}*g_{F(1,i-1)+F(j+1,2*n)} \]

Code

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include