题意: 有一个数p=1,甲乙两人轮流操作,每次可以把p乘2-9中的一个数,给定一个n,当一个人操作后p>=n那么这个人赢,问先手是否必胜.
必胜状态:存在一种走法走到一个必败状态.
必败状态:后继状态都为必胜状态.
我们可以知道>=n的数都为必败状态,可以转移到>=n的最小的数为n/9(上取整),所以 n/9~n-1都为必胜态,同理n/9/2(都为上取整)为最小的必须转移到n/9-n-1(必胜状态)的状态,所以n/9/2~n/9-1为必败态,于是就可以这样推到1,看一下1是必胜态还是必败态输出即可.
poj