题意

在环上分布着 $2n$ 个点，保证对于任意一个六元组 $(a,b,c,d,e,f)$，线段 $ab,cd,ef$ 三点不交于一线。

还给出了一个 $2n \times 2n$ 的矩阵 $A$。现在你要讲这 $2n$ 个点两两配对，满足以下条件：

• 每一对点之间都连线，以交点为点，所有交点之间的线段为边，构成的图是一棵树
• 如果配对 $(u,v)$，必须满足 $A_{u,v} = 1$

$n \leq 20$。

题解

细节上差了一点，还是菜了。

观察一下这个东西，我们考虑点 $1$ 连向点 $m$，那么跨过 $(1,m)$ 的线段有一些很好的性质：两个端点都是单调的。那么划分成子问题后大概长的就是一段圆弧+一条从外面连进来的边。这启发我们尝试对这个状态搞一下。

设 $f_{l,r,x}$ 表示编号在 $[l,r]$ 的圆弧，其中 $x \in [l,r]$ 与圆外的点配对连边的方案数。

转移我们考虑最上面（也就是最靠近端点处）的横跨 $(l,r)$ 的点对是什么，设它是 $(a,b)$。当时我到这里就意味可以直接转移，结果发现这样并没有保证联通的条件。。

想要保证联通，我们要认识一下怎么样能联通。想要把问题分成多个部分，我们必须要尝试保证 $[a+1,b-1]$ 中的点和两边的点是联通的。我们发现，从两边到中间，一定是先有一段通过和边 $(a,b)$ 相交而联通，后面就是保证与 $(?,x)$ 间接联通了。（如果不单调会成环）。所以我们再去枚举这两个边界，设其为 $l',r'$。

那么转移就是：

$$ f_{l,r,x} = \sum_{a,b,l',r'} f_{l,l',a} \times f_{l'+1,r'-1,x} \times f_{r',r,b} $$

复杂度 $O(n^7)$ 但是常数不大。

代码

#include <bits/stdc++.h>

#define fi first
#define se second
#define DB double
#define U unsigned
#define P std::pair
#define LL long long
#define LD long double
#define pb emplace_back
#define MP std::make_pair
#define SZ(x) ((int)x.size())
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

const int MAXN = 40 + 5;
int a[MAXN][MAXN];
char str[MAXN];
int n;
LL f[MAXN][MAXN][MAXN];

inline LL dp(int l,int r,int p){
    if(l == r) return p==l;
    LL &ans = f[l][r][p];
    if(ans != -1) return ans;
    ans = 0;
    FOR(i,l,p-1){
        FOR(j,p+1,r){
            if(!a[i][j]) continue;
            FOR(x,i,p-1){
                FOR(y,p+1,j){
                    ans += dp(l,x,i)*dp(x+1,y-1,p)*dp(y,r,j);
                }
            }
        }
    }
    return ans;
}

int main(){
    scanf("%d",&n);n <<= 1;
    FOR(i,1,n){
        scanf("%s",str+1);
        FOR(j,1,n) a[i][j] = str[j]-'0';
    }
    CLR(f,-1);
    LL ans = 0;FOR(i,2,n) if(a[1][i]) ans += dp(2,n,i);
    printf("%lld\n",ans);
    return 0;
}