题目大意
给定一个不严格凸的多边形, 求其三角剖分的数量, 其中切出的三角形面积不能为 $0$, 同时也不要求完全切完.
解法概要
容斥原理其实就是凑某个权函数, 我们直接思考这里的权是怎么凑的. 对于任意连续的 $k$ 条边, 我们假设有 $[x^{k}] F(x)$ 这么多种方案将 $k$ 条边当做一条边处理, 换句话说, 对于一条包含 $a_{i}$ 个线段的边, 我们有 $P_{a_{i}}(x) = [t^{a_{i}}]\frac{1}{1 - xF(t)}$, 有 $[x^{r}]$ 中方法将其当做 $r$ 条边来处理. 我们最后将乘积 $\prod\limits_{i}P_{a_{i}}(x)$ 算出之后, 将系数和 Catalan 数点乘.
为了让答案是对的, 我们要正确地设置 $F$, 为此我们要看贡献是怎么累计的. 考虑全体三角剖分, 允许留下 $0$ 面积三角形, 那么这样一个方案会被统计多少次呢? 把所有零面积三角形去掉, 对于每条边的端点, $a_{i}$ 会被拆成一些正整数的和, 一个 $k$ 会算做 $[x^{k}] G(x)$ 种方案. $G$ 是什么呢? 是它实际下面有多少种划分成 $0$ 面积三角形的方案, 也就是
$$G = F + G^{2}.$$
我们需要让 $G$ 是什么呢? 根据题面, 任何正整数长度都是允许的, 所以
$$G = \frac{x}{1 - x}.$$
那么
$$F = \frac{x(1 - 2x)}{(1 - x)^{2}}.$$
由于外层有个分治 FFT, 所以复杂度已经被冲到 $O(A\log^{2}A)$ 了. 所以在怎么求 $[t^{a_{i}}]\frac{1}{1 - xF(t)}$ 这一块, 预计的是大家各凭本事, 如果完全没有本事也能获得 $50$ 分. std 则是直接找出了一个整式递推式, 具体递推式长什么样子还请看代码.
若干注记
- Remark 1 从 analysis 可以看出, 本题的题面是很灵活的, 最开始的想法是让 $G = x$, 也就是不能有退化成三角形的多边形, 但是这样的话容斥系数更容易被猜出来, 所以未被采用, 于是将 $G$ 微操得到了现在的题面.
- Remark 2 预计的情况是好几个 $\geq 50$ 的人, 过 $100$ 的人预计是用一些需要 FFT 但是好写的做法来求的 $[t^{a_{i}}]\frac{1}{1 - xF(t)}$. 实际情况是一个 $50$ 分一个 $100$ 分 (qazswedx), 好像是维护了一个二维整式递推啥的. 看来我对现在大家的下限和上限都估计的不太准确...
- Question 1 有哪些多项式族 $F_{i}(x)$ 满足 $\prod\limits_{i}F_{i}(x)^{c_{i}}$ 的计算可以在非平凡的时间内解决? 例子是 $F_{i}(x) = F(x^{i})$. 或者解决其弱化版, 如果 $\sum ic_{i} = A$, 在 $o(A\log^{2}A)$ 内解决?
多余的话
- 这题是逆向工程的产物. 出题的时候起点是如何设计一个 $n^{3}$ 的区间 DP 可以做, 但是有更快的做法的数数题, 然后就对着造了一个题意.
- 这题是 考前 4 天 才得知要出的.