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]