500pt FiveHundredEleven
给出N(N<=50)个不小于0且不大于511的整数. 开始时寄存器为0, 两人轮流选取一个数, 与寄存器的值OR, 把结果覆盖写入寄存器. 数不能重复使用. 如果某人操作之后寄存器的值为511, 或者轮到某人时数都取完了, 那么这个人就算负. 问先手是否有必胜策略.
容易想到2^9这一维, 记录当前每一位的0/1状态. 实际上, 不需要记录当前已经选过哪些数, 而只用记录已经选了几个数, 再由当前的0/1态, 就能推算出哪些数没选过. 有些数x满足x|now != x, 这些数肯定没选过. 而对那些x|now == x的数, 不必知道它具体的值, 因为它对后续操作的影响都一样, 就是延缓一步, 把局面原封不动地丢给对方. 所以只需知道当前还有多少个这样的x没被使用过, 这个值也能由上面的信息得到.
这样就是一个类似极大极小的必胜必败态记忆化搜索.
状态为dp[1<<9][N], 转移为N.

[状态DP]

1000pt GameOfLifeDivOne
一个长为N(N<=50)的串(环状, 首尾相连, 即x[N-1]与x[0]相连), 由'0', '1' 和'?'组成, 其中'?' 处可以填上'0'或'1'. 从T=0开始, 每过1单位时间, 整个串会更新一次: 某一位, 如果上一时刻, 它, 以及与它相邻的两位, 一共有至少2个'1', 那么这一时刻它变成'1', 否则它变成'0'. 问共有多少种填'?'的方法, 使得在经过T(T<=1000)时间后, 还有不少于K(K<=N)个'1'. 比如'101010'->'010101'->'101010'->...; '11010'->'11101'->'11111'->...

首先容易观察到, 两个或两个以上连续相同的位是永远不会变的. 只有01交替的子串才会发生变化. 所以任意一个串都可以看成是若干个形如 xpy的子串首尾连接而成, 而且两串的首尾要相同才能连起来, 就像[xp1y][yp2x][xp3x][xp4y].... 其中pk是01交替序列, x和y都是一位, 可能是'0'或'1'. 特别的,连续3个相同字符可以看成是xx和xx粘起来(有1位重叠). 对于一个首尾字符固定不变的01交替串, 它在T时间后有多少个'1'是很容易算的. 两头都是0的话, 如0101010->0010100->0001000, 每时间减少一个1; 两头都是1的话类似, 每时间增加一个1. 一头是0一头1, 则0和1的个数都不变, 如010101->001011->000111. 
这样就有个算法的雏形, 类似背包: dp[pos][bit][one]表示: 从0到pos-1的子段, 以bit结尾, 且T时间后包含one个1的方法数. 如果从pos到某一位pos2-1, 能构造出以bit起始, 以bit2结束的交替串, 那么从状态dp[pos][bit][one]就能扩展到dp[pos2][bit2][one+one2], 则把前者加到后者上去, 其中one2是pos到pos2-1这个子串T时间后1的个数. 把原始串复制两遍, 就能比较方便地处理环. 
枚举在原串中首次出现连续2个相同字符的位置startpos, 对每个startpos做一次上述DP. 把所有one>=K的方法数加起来即可. 此外要先预处理出任意edg[i][b1][j][b2], 即从i到j-1能否构造出以b1开始, b2结尾的交替串, 如果能, T时间后有多少个'1'. 
其实整个题就是一道背包DP, 求用若干个短棍子, 拼出一个权值>=K的长棍子的方法数. 只是模型隐藏得很巧妙. orz...

[背包DP]