[300iq Contest 3] Airplane Cliques

Kubic · 2022-09-09 10:56:17 · 个人记录

一个与题解差别较为巨大的 O(n\log n) 做法，不需要神秘数据结构。

首先考虑 m 为偶数的情况。

显然对于任意一个合法集合 S 都存在至少一个 u 满足 \forall x\in S,dis(u,x)\le\dfrac{m}{2}。

此时的一个显然想法就是直接对每个 u 求出 a_u 表示与 u 距离不超过 \dfrac{m}{2} 的点数，然后对于每个 i 求 ans_i=\sum\limits_u\dbinom{a_u}{i}。

但这样算显然不对，某些 S 会被重复计算。

我们发现对于每一个 S，将它计入答案的 u 一定是树上的一个连通块。而这启发我们可以用经典的 |V|-|E|=1 进行处理。

考虑这个连通块中每一条边 e，那么它一定满足 \forall x\in S,dis(x,e)\le\dfrac{m}{2}-1。其中 dis(x,e) 表示 x 与 e 的两个端点的距离的较小值。可以证明这是充要条件。

因此我们对每条边 e 求出 b_e 表示与它距离不超过 \dfrac{m}{2}-1 的点数。

答案即为：ans_i=\sum\limits_u\dbinom{a_u}{i}-\sum\limits_e\dbinom{b_e}{i}。

再考虑 m 为奇数的情况。我们考虑先按照偶数的做法求出 m-1 的答案再进行调整。

考虑怎么求这个变化量。相当于要求出有多少个合法点集 S，满足 S 中距离最远的两个点的距离恰好为 m。

可以发现，对于这种 S 一定恰好存在一条边 e 满足 \forall x\in S,dis(x,e)\le\dfrac{m-1}{2}。

依然考虑枚举 e，但这时多出了一个限制要求在 e 的两侧各选了一个与它距离恰好为 \dfrac{m-1}{2} 的点。可以通过容斥解决，转化为 O(1) 个组合数的带权和。

现在我们求出了一个序列 f，答案即为 ans_i=\sum\limits_{j=0}^nf_j\dbinom{j}{i}。

根据 f 推出 ans 只需要一次卷积。而前面的各个值也可以利用点分治以及 dfs 在 O(n\log n) 的时间内求出。因此总时间复杂度 O(n\log n)。

这个做法相比题解虽然讨论的时候较为麻烦，但是直接做就是 O(n\log n)。而题解里的数据结构部分直接做是 O(n\log^2 n)，我还并不知道怎么优化到 O(n\log n)。