一维反Nim游戏

无心人

先罗列结果
2，3， 5，6，7，8先手胜，1，4先手负
(1, 1), (1, 2), (1, 3),先手胜
(2, 2) (3, 3)先手负
由几个先手负得到下面的几个先手胜
(2, 3), (2, 4), (1, 4),（3,4)，(3,5)

[ 本帖最后由 无心人 于 2008-9-11 20:45 编辑 ]

shshsh_0510

如果20#没算错的话，Z1=4的所有奇异局势为：
p4
o1p4,p2p4,p3p4, p1o4,o2o4,o3o4
p1o2p4,p1o3p4,p2p3p4,o1o2o4,o1o3o4
p1o2o3p4,o1p2p3p4, ,p1p2p3o4,o1o2o3o4,
Z1<=4的所有奇异局势为：
p1,o2,o3,p4
o1o2,o1o3,o2o3,o2o4,o3o4,p2p4,p3p4, p1o4, o1p4
o1o2o3,p1p2p3, p1o2p4,p1o3p4,p2p3p4,o1o2o4,o1o3o4
p1o2o3p4, o1p2p3p4, ,p1p2p3o4, o1o2o3o4
有点规律，但挺难描述

[ 本帖最后由 shshsh_0510 于 2008-9-11 17:34 编辑 ]

mathe

假设p4奇异,那么p2p4奇异肯定有错,应为对于1个2和1个4的情况,可以取掉2只余下4的.

shshsh_0510

check了一下，确实有bug ：）不过改完感觉更好了，去掉了看着很不爽的p2p4,p3p4
p4，
o1p4, p1o4,o2o4,o3o4
p1o2p4,p1o3p4,p2p3p4,o1o2o4,o1o3o4
p1o2o3p4,o1p2p3p4, ,p1p2p3o4,o1o2o3o4,

shshsh_0510

太容易出错，需要编个程序验证一下

mathe

我现在觉得除了1和4以外，都是先手必胜。

mathe

定义一个表格:
s[1]=1
s[2]=2
s[3]=3
s[4]=0
s[5]=1
s[6]=3
s[7]=4
s[8]=1
s[9]=6
s[10]=3
s[11]=2
s[12]=1
s[13]=6
s[14]=2
s[15]=4
s[16]=6
s[17]=7
s[18]=4
s[19]=3
s[20]=1
s[21]=7
s[22]=3
s[23]=8
s[24]=1
s[25]=6
s[26]=5
s[27]=4
s[28]=9
s[29]=6
s[30]=4
s[31]=3
s[32]=6
s[33]=1
s[34]=4
s[35]=5
s[36]=6
s[37]=10
s[38]=5
s[39]=2
s[40]=1
s[41]=10
s[42]=11
s[43]=4
s[44]=6
s[45]=11
s[46]=4
s[47]=3
s[48]=8
s[49]=1
s[50]=10

然后对于任意一个状态下，只要不是全部1或1个1和1个2的情况，对于其余情况，如果分成k堆，每堆分别有$x_1,x_2,...,x_k$个
那么对应状态数就是$s[x_1]"^"s[x_2]"^"..."^"s[x_k]$，只有那些状态数为0的状态才是先手负的。

上面的猜测还没有验证

mathe

而那几个特例是奇数个1状态数为0，偶数个1状态数为1，1*2+1*1状态数为1

mathe

晕，好像上面结论还是不行。因为两个4的情况不对。看来最大数据在4一下的都要枚举出来，可能5以后才能有比较好的规律，这样的话，最终结果还是很难求出来

无心人

俺重新描述下题目
有元素序列S，里面是正整数的从小到大排列
每个序列有状态胜和负
如果有序列s中元素k
1、当k <= 2，去掉元素k，得到的序列重新排列后得到序列s1
2、当k >= 2，用k - 1代替k，得到的序列重新排列后得到序列s1
3、当k >= 3，用k - 2代替k，得到的序列重新排列后得到序列s1
4、当k >= 3，把k分裂成两个元素k1, k2，且使得k = k1 + k2 + 1，得到的两个元素代替k进入序列，重新排列得到序列s1
5、当k >= 4，把k分裂成两个元素k1, k2，且使得k = k1 + k2 + 2，得到的两个元素代替k进入序列，重新排列得到序列s1
所有满足条件1，2，3的序列s1称为s的直接子序列，其集合称为s的直接子序列集合

定义，只有且仅有偶数个1的序列状态是胜，只有且仅有奇数个1的序列状态是负
则，如果序列的直接子序列有一个序列状态是负，则序列的状态是胜
如果序列的直接子序列集合中的所有序列状态均是胜，则序列状态是负

呵呵，这么写，清楚了么？
而且似乎可以用来计算吧