[SDOI / SXOI2022] 多边形 解析

题目大意

给定一个不严格凸的多边形, 求其三角剖分的数量, 其中切出的三角形面积不能为 /(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 = 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_i F_i(x)^{c_i}/) 的计算可以在非平凡的时间内解决? 例子是 /(F_i(x) = F(x^i)/). 或者解决其弱化版, 如果 /(/sum ic_i = A/), 在 /(o(A/log^2 A)/) 内解决?