题目大意

给定一个不严格凸的多边形, 求其三角剖分的数量, 其中切出的三角形面积不能为 \(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_i P_{a_i}(x)\) 算出之后, 将系数和 Catalan 数点乘.

为了让答案是对的, 我们要正确地设置 \(F\), 为此我们要看贡献是怎么累计的. 考虑全体三角剖分, 允许留下 \(0\) 面积三角形, 那么这样一个方案会被统计多少次呢? 把所有零面积三角形去掉, 对于每条边的端点, \(a_i\) 会被拆成一些正整数的和, 一个 \(k\) 会算做 \([x^k] G(x)\) 种方案. \(G\) 是什么呢? 是它实际下面有多少种划分成 \(0\) 面积三角形的方案, 也就是

我们需要让 \(G\) 是什么呢? 根据题面, 任何正整数长度都是允许的, 所以

那么

由于外层有个分治 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_i F_i(x)^{c_i}\) 的计算可以在非平凡的时间内解决? 例子是 \(F_i(x) = F(x^i)\). 或者解决其弱化版, 如果 \(\sum ic_i = A\), 在 \(o(A\log^2 A)\) 内解决?