Project Euler 306

发表于 更新于 分类于 阅读次数： 本文字数： 2k 阅读时长 ≈ 2 分钟

Project Euler 306

题目

Paper-strip Game

The following game is a classic example of Combinatorial Game Theory:

Two players start with a strip of \(n\) white squares and they take alternate turns.

On each turn, a player picks two contiguous white squares and paints them black.

The first player who cannot make a move loses.

  • \(n = 1\): No valid moves, so the first player loses automatically.
  • \(n = 2\): Only one valid move, after which the second player loses.
  • \(n = 3\): Two valid moves, but both leave a situation where the second player loses.
  • \(n = 4\): Three valid moves for the first player, who is able to win the game by painting the two middle squares.
  • \(n = 5\): Four valid moves for the first player (shown below in red), but no matter what the player does, the second player (blue) wins.

So, for \(1 \le n \le 5\), there are \(3\) values of \(n\) for which the first player can force a win.

Similarly, for \(1 \le n \le 50\), there are 40 values of \(n\) for which the first player can force a win.

For \(1 \le n \le 1 000 000\), how many values of \(n\) are there for which the first player can force a win?

Sprague–Grundy定理

\(sg\)函数是一个用来解决公平组合游戏(ICG)问题的一种工具。

定义一个非负整数集合上的运算\(\text{mex}(s)\)：表示集合\(s\)中未出现的最小的非负整数。

我们定义一个游戏状态\(n\)，令\(sg(n)=\text{mex}(\{sg(m)|n\rightarrow m\})\).\(m\)是从\(n\)能够抵达的所有游戏状态。如果\(sg(n)>0\)，那么状态\(n\)为必胜态；如果\(sg(n)=0\)，那么为必败态。

Sprague–Grundy，SG定理说明了，如果这个游戏当前的状态\(n\)，它可以看做是多个状态\((n_1,n_2,\dots,n_k)\)的组合，那么就可以写成：

\[sg(n)=sg(n_1)\oplus sg(n_2)\oplus \dots \oplus sg(n_k)\]

以NIM游戏为例，如果当前有\(n\)堆石头，其中第\(i\)堆为\(a_i\)。那么状态\(sg(a_1,a_2,\dots,a_n)\)可以看成是\(sg(a_1),sg(a_2),\dots,sg(a_n)\)的组合，当前的状态是必胜态还是必败态由\(sg(a_1)\oplus sg(a_2)\oplus\dots\oplus sg(a_n)\)决定。

因此一般使用SG定理解决问题，主要依靠的是分治的思想。

解决方案

当双方每一次占用相邻的格子时，可以把它看成是将一个长度为\(n\)的纸条，将其中相邻的两格占用后，产生了两个长度分别为\(i,n-2-i(0\le i\le n-2-i)\)的纸条。

因此我们可以将一个长度为\(n\)的纸条看做是一个状态，设其为\(sg(n)(n\ge 0)\).那么\(sg(n)\)的值就可以通过以下值计算出：

\[ sg(n)= \left \{\begin{aligned} &0 & & \text{if}\quad n\le 1 \\ &\text{mex}(\{sg(i)\oplus sg(n-2-i)|0\le i\le n-2-i\}) & & \text{else} \end{aligned}\right. \]

使用如下代码打印出这个游戏的\(sg\)函数前一部分序列，在OEIS中查询到结果为A002187。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
const int N=100;
int sg[N+4];
bool mex[N+4];
int main(){
    for(int i=1;i<=N;i++){
        memset(mex,0,sizeof(mex));
        int j=0;
        for(j=0;j<=i-j-2;j++)
            mex[sg[j]^sg[i-j-2]]=1;
        for(j=0;mex[j];++j);
        sg[i]=j;
    }
    for(int i=0;i<=N;i++)
        printf("%d ",sg[i]);
}

在FORMULA一栏中查找到这个信息：

1
Has period 34 with the only exceptions at n=0, 14, 16, 17, 31, 34 and 51.

这说明这个\(sg\)函数是一个以\(34\)为周期的序列，除了\(0,14,16,17,31,34,51\)这几个状态。

因此，计算时只需要单独考虑\(1\sim 51\)这几个项即可。

代码

1
2
3
4
5
6
7
8
9
10
11
N = 10 ** 6
a = [0, 1, 1, 2, 0, 3, 1, 1, 0, 3, 3, 2, 2, 4, 0, 5, 2, 2, 3, 3, 0, 1, 1, 3, 0, 2, 1, 1, 0, 4, 5, 2, 7, 4, 0, 1, 1, 2,
     0, 3, 1, 1, 0, 3, 3, 2, 2, 4, 4, 5, 5, 2]
t = [3, 3, 0, 1, 1, 3, 0, 2, 1, 1, 0, 4, 5, 3, 7, 4, 8, 1, 1, 2, 0, 3, 1, 1, 0, 3, 3, 2, 2, 4, 4, 5, 5, 9]
ans = sum(a[i] > 0 for i in range(min(N, len(a))))
if N > len(a):
    N -= len(a)
    block, res = divmod(N, len(t))
    ans += block * (len(t) - t.count(0)) + res - t[:res].count(0)
print(ans)