题意

平面上有 $m$ 个特殊点，每个点有一个颜色。还有 $n$ 个点均匀分布在半径为 $r$ 的圆上，认为有一个点在 $(r,0)$。现在问有多少种方式，可以在这些点之间连线，满足：

• 每个点度数是 $0$ 或 $2$
• 这些线段与点构成了若干个封闭的简单多边形，并且互不相交，互不包含
• 所有相同颜色的特殊点必须在同一个多边形内
• 每一个多边形内部至少要有一个特殊点
• 每一个特殊点至少要在一个多边形内部

问这样分配的方案数。对 $10^5+7$ 取模。

$m \leq 50,n \leq 222$，保证没有特殊点位于某个连线上。

题解

条件 $(1),(2)$ 实际上就是要求方案必须是若干个不交的简单多边形。

条件 $(3)$ 看上去不好处理，但是我们可以考虑这个条件实际上是对边的限制：一个边是合法的当且仅当两边不能都有某种颜色的点。所以可以预处理出哪些边是合法的。

现在重点是对后两个条件计数。由于这种东西看上去像是有分治结构（每次找到最外层的边，删掉之后里面和外面不会有连边），所以我们考虑区间 dp。

设 $f_{l,r}$ 表示只考虑编号在 $[l,r]$ 内的点，和连线 $l \to r$ 这里面的特殊点，安排合法的方案数。

转移的时候我们观察这个形式一定是形如若干个块，每块最外面都有一条边，然后块内都是一个独立的子问题。所以我们可以设 $g_{l,r}$ 表示这样的块的答案（也就是强制要求连边 $l \to r$ 的方案数），转移的时候我们可以枚举第一个块在哪里，也就有 $f_{l,r} = \sum_{l_1,r_1} g_{l_1,r_1} \times f_{r_1+1,r}$。但是要考虑限制（$(5)$），而这样走之后就会有一些多边形的点永远不会被包含，这里就是 $(l,l_1,r)$ 和 $(l_1,r_1,r_1+1,r)$ 这两个多边形。可以预处理每个直线左右的点的编号和颜色来快速判断。

那么考虑 $g_{l,r}$ 如何转移：由于限制 $(4)$ ，我们必须要走出一个至少包含一个特殊点的块。首先必须要求 $l \to r$ 是一个合法的边。然后观察现在的结构：我们实际上是要做一个，钦定必须连 $l \to r$，然后找到一些点 $v_1,v_2,\ldots,v_m$，使得这个多边形 $(l,v_1,v_2,\ldots,v_m,r)$ 都是合法的边，包含至少一个特殊点，并且这样会产生很多个不可能覆盖区域，比如 $(l,v_1,v_1-1,l+1),(v_1,v_2,v_2-1,v_1+1)$ 这样的区域，要求这些区域里不能有特殊点；然后就会递归成若干个子问题 $f(l+1,v_1-1),f(v_1+1,v_2-1),\ldots$ 。

直接枚举显然不可行，考虑再用一个 dp 去计算这个事情。发现这个判断过程中只需要知道上一个点是什么，和终点是什么（为了判断覆盖的区域）。所以我们考虑记录这个事情。设 $h_{l,r,0/1}$ 表示我们现在最后的一条边是 $l \to r$，当前覆盖的区域中是否已经出现了特殊点的方案数。转移枚举和当前点 $l$ 连边的位置 $t$，先要求这个边合法，然后判断 $(l,t,t-1,l+1)$ 是否没有点，然后乘上一个 $f(l+1,t-1)$，然后看一下新增的区域 $(l,t,r)$ 是否有特殊点来更新 $0/1$ 这一维就好了。

最终 $h$ 的终止状态显然是 $h(r,r,1)=1$。

这样复杂度是 $O(n^4)$ 的，瓶颈在于 $f_{l,r}$ 的转移，我们可以用一个经典套路来优化：我们求 $f(l,r)$ 的时候，我们先计算 $f(l+1,r)$，然后再去计算所有左端点是 $l$ 的 $(l_1,r_1)$，这样就只需要枚举 $r_1$ 了，复杂度降为 $O(n^3)$。注意在决策是否计算 $f(l+1,r)$ 的时候要判断区域 $(r,l,l+1)$ 是否有特殊点。

注意一开始要做一个特判：如果有的点在这个多边形的外边，那么答案就是 $0$。

代码

#include <bits/stdc++.h>

#define fi first
#define se second
#define DB double
#define U unsigned
#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 = 50 + 5;
const int MAXM = 222 + 5;
const int ha = 100007;
const DB pi = acos(-1);

inline void add(int &x,int y){
    x += y-ha;x += x>>31&ha;
}

int n,m,r;
LL s[MAXM][MAXM],c[MAXM][MAXM];
// 企鹅,颜色
int F[MAXM][MAXM],G[MAXM][MAXM],H[MAXM][MAXM][2];
bool v[MAXM][MAXM];
// f[l][r]: [l,r] 的答案
// g[l][r]: [l,r] 钦定 l,r 选的答案
// h[l][r][0/1]: [l,r] 钦定连 l->r ,是否找到了一个企鹅的方案

int f(int,int);
int g(int,int);
int h(int,int,int);

int f(int l,int r){
    if(l == r+1) return 1;
    if(l == r) return 1;
    if(F[l][r] != -1) return F[l][r];
    int &res = F[l][r];res = 0;
    if(!(s[r][l]&s[l+1][r])) res = f(l+1,r);
    FOR(k,l+2,r){
        if(s[r][l]&s[l][k]&s[k+1][r]) continue;
        add(res,1ll*g(l,k)*f(k+1,r)%ha);
    }
    return res;
}

int g(int l,int r){
    if(r-l+1 <= 2) return 0;
    if(G[l][r] != -1) return G[l][r];
    int &res = G[l][r];res = 0;
    if(v[l][r]) res = h(l,r,0);
    return res;
}

int h(int l,int r,int ok){
    if(l == r) return ok;
    if(H[l][r][ok] != -1) return H[l][r][ok];
    int &res = H[l][r][ok];res = 0;
    FOR(k,l+1,r){
        if(!v[k][l]) continue;
        if(s[k][l]&s[l+1][k-1]) continue;
        add(res,1ll*f(l+1,k-1)*h(k,r,ok||((s[k][r]&s[r][l]&s[l][k])))%ha);
    }
    return res;
}

const DB EPS = 1e-9;

inline int sgn(DB x){
    if(std::fabs(x) <= EPS) return 0;
    return x > 0 ? 1 : -1;
}

class FencingPenguins{
private:
    struct P{
        DB x,y;
        P(DB x=0,DB y=0) : x(x),y(y) {}
        P operator - (const P &t) const {return P(x-t.x,y-t.y);}
        DB det(const P &t) const {return x*t.y-y*t.x;}
    }a[MAXM],b[MAXN];
    int col[MAXN];

    DB cross(P a,P b,P c){
        return (b-a).det(c-a);
    }

    inline int ctoi(char c){
        if('A' <= c && c <= 'Z') return c-'A';
        return c-'a'+26;
    }

public:
    int countWays(int _n,int _r,std::vector<int> _x,std::vector<int> _y,std::string _col){
        n = _n;r = _r;m = SZ(_x);
        FOR(i,0,m-1) b[i] = P(_x[i],_y[i]),col[i] = ctoi(_col[i]);
        FOR(i,0,n-1) a[i+1] = P(r*cos(2*pi/n*i),r*sin(2*pi/n*i));
        FOR(i,1,n) FOR(j,1,n) FOR(k,0,m-1) if(sgn(cross(a[i],a[j],b[k])) >= 0) s[i][j] |= (1ll<<k),c[i][j] |= (1ll<<col[k]);
        FOR(i,2,n) if(s[i][i-1]) return 0;
        if(s[1][n]) return 0;
        FOR(i,1,n) FOR(j,1,n) v[i][j] = !(c[i][j]&c[j][i]);
        CLR(F,-1);CLR(G,-1);CLR(H,-1);
        return f(1,n);
    }
};