SD/XOI 2022 多边形

首先我们考虑不重不漏地统计这个事情，这个题事实上是凸多边形划分的一个拓展，传统的凸多边形剖分方案数就是卡特兰数。

那么这里的区别就是：

• 在一条边上的点不能相互连线段
• 在边中间上的点可以没线段

不妨考虑我们手动枚举了一些中间点完全不连边，剩下 (m) 个点要连边，如果我们直接当做凸 (m) 三角剖分数（设为 (T_m) ），会包含所有合法方案，但也会多算一些不合法方案，这些方案的特征是：包含至少一条两段点都在同一条边上的线段。

进一步，因为三角剖分是恰好剖完的，你可以想象把那条边上的点人为凸出去，那么只要有一条不合法线段，那么里面必然有一条线段恰好跨越一个点（称之为相邻不合法线段）！

那么我们就可以钦定一个相邻不合法线段的集合 (S) 去容斥，相当于把两条边缩成了一条边，忽略了中间一个点，中间有个 (-1^{|S|}) 的容斥系数就行了。

那么整体的框架就是：先抛去一些边中间的点不连边，然后在剩下的点中选出若干互不相邻的点减少一条边做容斥，最终乘上对应的三角剖分数。

每条边独立，设一条边中间有 (t) 个点，设 (F_i) 表示这条边中间最终保留下来 (i) 个点，计算我们就再枚举 (j) 个点作为容斥，方案数可以直接插板：

最后把每个 (F) 乘起来，然后乘上对应的卡特兰数加和就好了，这部分似乎必须要分治 NTT，看似是 (log^2) 但你发现极限情况是 (250000) 而不是 (500000)，好像可以接受？

然后就能 (O(n^2)) 了。

现在就是要快速算每个 (F)，发现他有 (i+j,i,i-j) 不能直接卷积，可恶！！

EI 好像会线性算，这里只提供两种拙劣的方法：

1. 可以直接按照组合意义，即分成若干最终保留的段，然后不保留段中可以选择一个作为容斥，然后类似倍增 DP / FFT 的过程做就好了，应该需要记录左右端点的状态，可能是 (O(9nlog n)) 的，不知道会不会 T。

2. 考虑 GF，这个过程很像二项式定理，配一个 (x) 可以画成两个 ((x+1)^p) 乘积的形式：

   [F_i = [x^{t-i}]sum_{j} binom{t}{t-i-j} x^{t-i-j} binom{i+1}{j}(-x)^{j} ]
   [= [x^{t-i}] (x+1)^t (1-x)^{i+1} ]
   [= [x^{t}] (x+1)^t [(1-x)^{i+1}x^i] ]
   [= sum_{j=0}^t [x^{t-j}](x+1)^t times [x^j][(1-x)^{i+1}x^i] ]

   设 (G_j = [x^{t-j}](x+1)^t)。

   [F_i = sum_{j=0}^t G_j times [x^j][(1-x)^{i+1}x^i] ]

   考虑使用转置原理，反过来看 (F) 到 (G) 系数向量的线性变换，以下 (h) 充当 (F) 作用：

   [G_j = [x^j]sum_{i=0}^a h_i [(1-x)^{i+1}x^i] ]

   设 $$H(x) = sum_{i=0}^a h_i x^i $$

   [= [x^j]sum_{i=0}^a (1-x)H(x-x^2)) ]
   [= [x^j]sum_{i=0}^a (1-x)H(-(x-frac{1}{2})^2+frac{1}{4})) ]

   将步骤拆解，可以概括为：

   • 将 (H(x)) 变成 (H(x+frac{1}{4}))
   • 将 (H(x)) 变成 (H(-x))
   • 将 (H(x)) 变成 (H(x^2))
   • 将 (H(x)) 变成 (H(x-frac{1}{2}))
   • 将 (H(x)) 乘 ((1 - x))

   每一步的转置矩阵，(1, 4) 步是卷积，剩下都可以线性做，就做到了 (O(n log n))

代码实现的第二种：

code