AT AGC043C - Giant Graph - 总结

发布时间 2023-11-12 17:47:00作者: xaocy

AT AGC043C - Giant Graph

因为 \({(10^{18})}^{x+y+z}\) 的底数很大,所以我们贪心的选择 \(x+y+z\) 大的点是存在正确性的。那么我们从小点向大点连有向边,形成 DAG 后,对于一个点,如果它指向的点都没有被选取,那么选择它,否则不选。

我们发现这样的选取过程和求 SG 函数是一样的,并且每次移动都只会改变一维,所以可以将整张图拆为三张原图,那么最后 \(\text{SG}(x,y,z)=\text{SG}(x)\ \otimes\ \text{SG}(y)\ \otimes\ \text{SG}(z)\)

我们只需要统计 \(\text{SG}(x,y,z)=0\) 的点权和就好了。