【BZOJ3576】【HNOI2014】江南乐

显然sg函数

那么对于\(x<F,sg(x)=0\)

对于\(x>=F\)枚举拆分情况

我们会发现,拆成偶数堆的异或一下就没了,拆成奇数堆的和拆成一个没有区别

那么只要考虑奇偶性。对于\(\lfloor\frac{x}{i}\rfloor\)相等的一段,拆分情况的奇偶性只和\(i\)的奇偶性有关。那么最多只需要考虑两个。

\(\lfloor\frac{x}{i}\rfloor\)的取值只有根号个,因此mex函数的复杂度也是根号的。

另外就是预处理的话在BZOJ上容易T。。最好记忆化搜索

说点什么

您将是第一位评论人!

提醒
wpDiscuz