• 欢迎光临~

SD/XOI 2022 多边形

开发技术 开发技术 2022-05-20 次浏览

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

那么这里的区别就是:

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

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

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

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

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

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

[F_i = sum_{j} (-1)^jbinom{t}{i + j} binom{i+1}{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

程序员灯塔
转载请注明原文链接:SD/XOI 2022 多边形
喜欢 (0)