取石头一

取石子游戏需要两名玩家和三堆石头。

每名玩家在自己的回合需要从石头堆中取走至少一个石子，玩家可以只从一个堆中取石头，但若玩家选择从多个堆中取走石头，则其从每个堆所取的石头数必须相同。

亦即玩家可以：从一个堆中取走N个石头，或从任意两个堆中每堆各取N个石头，或从所有三个堆中每堆各取N个石头，以上N均为正数。

取走最后一块石头的玩家获胜。

能使先手玩家必胜的初始石头分布称为必胜态，例如$(0,0,13), (0,11,11), (5,5,5)$都是必胜态，因为先手玩家在第一轮就能取走所有石头。

相应地，能使后手玩家必胜的初始石头分布称为必败态，例如$(0,1,2), (1,3,3)$都是必败态。

可以验证，所有满足$x\le y\le z\le100$的必败态$(x,y,z)$的石头总数之和$\sum x+y+z$为$173895$。

求所有满足$x\le y\le z\le1000$的必败态$(x,y,z)$的石头总数之和。

本题难度:

解答

容易看出，分析时只需考虑将某一堆石头取完时的状态转移。

以取第一堆中的石头为例，若$(0,y,z)$对我方有利，则显然应该取走全部x，否则若$(0,y,z)$对我方不利，本次取走$x-m$块石头，对手以$(m,y,z)$开始回合，那么对手只需取走m块石头，则下一回合我方仍需面对$(0,y,z)$的局面。

因此用三个列表分别记录从一、二、三堆中取石头的状态转移，并取初值$(0,0,0)$为必败态，递推计算即得结果$167542057$。

注：计算量较大，代码中打印了进度信息。

target=1001
d1=[[False]*target for i in range(target)]
d2=[[False]*target for i in range(target)]
d3=[[False]*target for i in range(target)]

r=0
for x in range(target):
    for y in range(x,target):
        for z in range(y,target):
            if not any([d3[y-x][z-y],d2[z][y-x],d2[y][z-x],d2[x][z-y],d1[y][z],d1[x][z],d1[x][y]]):
                d3[y-x][z-y]=d2[z][y-x]=d2[y][z-x]=d2[x][z-y]=d1[y][z]=d1[x][z]=d1[x][y]=True
                r+=x+y+z
    if x%10==0:print x/10,"percent completed"
print r