QOJ # 6354. 4

发布时间 2023-08-25 21:42:41作者: 275307894a

题面传送门

我是傻逼。

首先你看这东西长得一脸四元环计数那类东西,于是先给边定向,这样子的话就形成了一张图,每个点只有 \(O(\sqrt m)\) 条出边。

现在我们枚举一个三元环,要计算三个点都指向的点的个数。

直接做有 \(O(m\sqrt m)\) 个三元环,每个三元环需要 \(O(\frac{m}{\omega})\) 统计贡献,不太行。

注意到一个点的出边只有 \(O(\sqrt m)\) 条,并且三元环上另外两个点和这些点都指向的那个点都在这 \(O(\sqrt m)\) 条出边指向的点中,所以实际上 bitset 中点的个数只有 \(O(\sqrt m)\) 个,所以总复杂度是 \(O(\frac{m^2}{\omega})\) 的。

submission