CF437E The Child and Polygon

发表于 分类于 ， ， 阅读次数：

题意：给出一个 个点的多边形，求其三角剖分的方案数。

答案对 取模，，时限 。

将多边形上的点逆时针编号为 。

设 为：存在边 ，点 的三角剖分方案数。

转移时，可以枚举点 剖出三角形 ，将目前的点集划分成 。如果这个三角形有任何一部分在多边形外，则不合法。

转移总量是 的，判定一条线段是否有一部分在多边形外是 的，无法通过。

若多边形上的点逆时针排序，考虑只判断 是否在向量 右侧。

这样，就算这一次允许了不合法的转移，接下来 必然没有合法方案，所以不会产生不合法的贡献。

这样就做到了 。

这种让转移的约束具有传递性的思路，还是挺难想的。