请求撤下题解
查看原帖
请求撤下题解
1013881
do_it_tomorrow楼主2024/9/11 20:50

这篇题解认为 SG 函数的值为 tt 的 DAG 至少应该有 O(t2)O(t^2) 个节点,并且还通过了他错误的证明得出了这个结论。

事实上可以构造出一下的 DAG 让节点的数量与 SG 函数在同一级别,DAG 的 SG 函数应该是 O(m)O(\sqrt{m}) 的。

虽然本题中 n,mn,m 同阶,但是这个题解的证明未免有些太离谱了,而且很具有误导性,故请求撤下。

2024/9/11 20:50
加载中...