Project Euler #409 Nim Extreme

2019-03-11

极限取石子游戏

记 n为正整数。考虑如下的取石子游戏设计:

  • 有n个非空的堆。
  • 每个堆的石子数小于2n
  • 没有两堆的石子数相同。

记W(n)是所有设计中必胜态的数目(必胜态是指先手玩家有必胜策略的状态)。例如,W(1) = 1, W(2) = 6, W(3) = 168, W(5) = 19764360,以及W(100) mod 1000000007 = 384777056。

求W(10000000) mod 1000000007。


最开始被值域误导了,认为每次值域翻一倍可以用于解决问题,但事实上并没有用。

考虑DP。

令\(F[i]\)表示i堆石子的答案,\(all[i]\)表示\(i\)堆石子互不相同的方案数,\(v\)是值域范围。

我们考虑第i堆石子有多少种取值方法:不能与前\(i-1\)堆相同,不能等于前\(i-1\)堆的异或和。

我们分三种情况讨论:

1)异或和等于某堆石子个数:

这时除去这堆石子剩下\(i-2\)堆的异或和是\(0\),方案数就是\(all[i-2]-f[i-2]\)。

所以有\(F[i]=(i-1)*(all[i-2]-F[i-2])*(v-i+2)*(v-i+1)\)。

2)异或和等于\(0\):

前\(i-1\)堆方案数为\(all[i-1]-F[i-1]\),

\(F[i]=(all[i-1]-F[i-1])*(v-i+1)\)。

3)其他情况:

前\(i-1\)堆异或和不为\(0\)且不和任一堆相同,方案数是\(F[i-1]-(i-1)*(all[i-2]-F[i-2])*(v-i+2)\),

\(F[i]=[F[i-1]-(i-1)*(all[i-2]-F[i-2])*(v-i+2)]*(v-i)\)。

 

Leave a Reply:

电子邮件地址不会被公开。 必填项已用*标注