题意
平面上有 $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);
}
};