hdu 1850 Being a Good Boy in Spring Festival (nim游戏问必胜方案数,sg函数)

hdu1850题目链接
题意:n堆石子。。每堆可以取任意多个。。。先取完的赢。。问先手能否赢。。能赢的话第一步有几种取法。。
思路:sg函数。。对于方案数,可以用nim游戏的结论。

未命名。设异或和为sum..那么统计满足 a[i]^sum<a[i]的个数就是第一步能走的方案数。

以及。。sg函数。。如果走的步数是任意的。。也就是没有限制。。。那么sg[i] = i…此时也就退化成了一般的nim游戏。。。

 

 

作者: CrazyKK

ex-ACMer@hust,researcher@sensetime

说点什么

您将是第一位评论人!

提醒
wpDiscuz