AGC043C Giant Graph

题意 ： 给出三张无向图 ，点数均为 ，点的标号为 。

建立一张大图 ，其中点为三元组 ，其中 。

• 对于 中的边 ，在 与 之间连边。

• 对于 中的边 ，在 与 之间连边。

• 对于 中的边 ，在 与 之间连边。

点 的权值定义为 。

求图 的最大独立集权值和，答案对 取模。

，时限 。

---

由于 非常大，我们可以按照 的顺序从大到小贪心考虑。

不难发现，对于 相同（权值相等）的点，之间必然没有边，互不影响。

• 于是如下的贪心是正确的 ：

  从大到小枚举点（权值相同顺序任意），贪心选择。

赛时到这里就没思路了。

考虑进一步抽象这个贪心，发掘性质。

我们为边定向，从小点连向大点，图变为了 DAG。

从大到小考虑（也是按照拓扑序从后往前考虑）若出边到达的点均没有标记，将其加入最大独立集，并打上标记。

可以发现，这和博弈论中的 态的定义同构。在这个 DAG 中， 态即为最大独立集。

考虑如何快速判定 是否为 态。观察到三个维度可以分别移动，且每一步只能移动一维，等同于三个游戏之和。

求出三张图中各个点的 值 。

则答案为 ：

异或卷积即可。复杂度为 。

• 结论 ： DAG 的 函数的上界为 。

  于是可以 进行暴力异或卷积。