QOJ # 7514. Clique Challenge

发布时间 2023-10-03 08:27:47作者: 275307894a

题面传送门

为啥我会在想多项式做法啊?

首先考虑稠密图怎么做,也即 \(n=O(\sqrt m)\) 的图。将点分为前一半后一半,然后 meet in middle,其中一边用高维前缀和即可做到 \(O(n2^{\frac{n}{2}})\) 的复杂度。

然后我们需要将其扩展到可能稀疏的图上。仿照三元环计数的方法,将其按照度数排序,然后强制每条边从度数小的点指向度数大的点。这样子每个点的出度不会超过 \(\sqrt {2m}\) 。枚举团内度数最小的点,然后将这个点的出边所有的点进行一次 meet in middle。这样子的复杂度是 \(O(m 2^{\frac{\sqrt {2m}}{2}})\) 的,应该可以证明到 \(O(\sqrt m 2^{\frac{\sqrt {2m}}{2}})\)

submission