500pt Perfect Memory
題意: 某神在M*N(1<=M, N<=50, M*N為偶數(shù))的格子上玩對對碰: 每個(gè)格子都有個(gè)隱藏的圖形. 此神一次行動翻開2個(gè), 如果相同, 就成功消去這2個(gè)格子. 如果不相同, 那這2個(gè)格子又恢復(fù)隱藏狀態(tài). 但是此神記憶力很NB, 能記住所有翻開過的格子是什么圖形. 還有重要的一點(diǎn), 他一次行動時(shí), 是先翻開1個(gè)格子, 知道它的圖形之后, 再決定怎么翻第2個(gè)格子, 而不是兩個(gè)格子同時(shí)翻開. 問此神把所有格子都消去, 需要消耗的行動次數(shù)的期望.

容易想到期望與翻格子的位置無關(guān). 有關(guān)的量是: 當(dāng)前還有多少對圖形沒被消去. 其中有多少對圖形已經(jīng)知道其中一個(gè)的位置了. so, dp[i][j], i為前者, j為后者. 一次行動中, 第1個(gè)格子肯定翻之前沒翻過的(一共有2i-j個(gè), 記為s), 除非已經(jīng)知道某1對的位置, 直接把2個(gè)都翻出來消掉. 所以轉(zhuǎn)移有幾種情況:
1) 從s中翻出1個(gè)新圖形. 從剩下s-1中翻出了相同圖形, 消除. 這樣的概率是2(i-j)/s * 1/(s-1), 轉(zhuǎn)移到dp[i-1][j].
2) 從s中翻出1個(gè)新圖形. 從剩下s-1中又翻出新圖形, 這樣就多了2種已知圖形. 概率是2(i-j)/s * 2(i-j-1)/(s-1), 轉(zhuǎn)移到dp[i][j+2].
3) 從s中翻出1個(gè)新圖形. 從剩下s-1中翻出了之前j個(gè)已知圖形中的一個(gè). 這樣, 下一次就可以消耗一次行動把那對已知圖形消去, 轉(zhuǎn)移到dp[i-1][j], 概率是2(i-j)/s * j/(s-1).
4) 從s中翻出1個(gè)已知圖形. 直接翻出與它配對的消去. 轉(zhuǎn)移到dp[i-1][j-1], 概率是j/s * 1.

所以 dp[i][j] = p1*(dp[i-1][j]+1) + p2*(dp[i][j+2]+1) + p3*(dp[i-1][j]+2) + p4*(dp[i-1][j-1]+1).
其中2)的條件是i>=j+2, 4)的條件j>=1. 邊界dp[i][i] = i. 最后dp[M*N][0]即為所求.

[概率 期望 DP]

1000pt Reflections
題意: 某神在三維空間中玩一個(gè)游戲, 空間中有N個(gè)(N<=20)平面, 每個(gè)平面都垂直于某個(gè)坐標(biāo)軸, 并且與該坐標(biāo)軸交于整點(diǎn). 此神從(0,0,0)處出發(fā), 想去(X,Y,Z)處. 現(xiàn)在他每行動一次可以做如下移動:
1) 走到與他相鄰的1個(gè)整點(diǎn)上, 即(x+1, y, z) (x-1, y, z) (x, y+1, z) (x, y-1, z) (x, y, z+1) (x, y, z-1)中的一個(gè).
2) 神一次行動可以利用一個(gè)平面, 移動到關(guān)于這個(gè)平面對稱的點(diǎn)處. 每個(gè)平面在整個(gè)游戲過程中至多只能利用一次.
問此神到達(dá)終點(diǎn)花費(fèi)的最少行動次數(shù).

易知三個(gè)方向是不相關(guān)的. 所以只用先考慮一維的情形.
首先要想到, 走路和反射交替, 是等效于先反射完了再一口氣走到終點(diǎn)的. 因?yàn)樵诜瓷渲暗淖邉? 不會被反射動作放大. 反射前移動多少步, 經(jīng)過若干次反射后所到達(dá)的位置, 與不移動直接反射到達(dá)的位置, 相差正好是移動的步數(shù).
所以可以轉(zhuǎn)化為先反射若干次, 再行走到終點(diǎn). 現(xiàn)在就要推出反射到達(dá)的位置公式.
假設(shè)每個(gè)反射軸的坐標(biāo)依次是x[1], x[2], ..., x[n], 神經(jīng)過第k次反射后的位置是p[k].
容易推出, p[1] = 2x[1], p[2] = p[1] + 2(x[2]-x[1]) = 2x[2] - 2x[1], ... p[k] = 2x[k]-2x[k-1]+2x[k-2]-...+2*(-1)^(k-1)x[1].
這是很規(guī)則的正負(fù)交替求和, 正項(xiàng)數(shù)等于負(fù)項(xiàng)數(shù), 或者比負(fù)項(xiàng)數(shù)多1.
到此問題轉(zhuǎn)化得很清晰了: 在20個(gè)數(shù)中選出k個(gè)數(shù)作為正項(xiàng), k(或k-1)個(gè)數(shù)作為負(fù)項(xiàng), 每個(gè)數(shù)至多被選1次. 該方案的總行動次數(shù)是選出的個(gè)數(shù)(即做反射的總次數(shù)), 加上這些項(xiàng)之和到終點(diǎn)的距離(即最后一路走過去). 
選數(shù)要降低復(fù)雜度, 可以把20個(gè)數(shù)分成兩個(gè)集合, 每邊10個(gè)數(shù), 先各自生成2^10個(gè)和. 兩邊分別排序后, 從小到大枚舉左邊的, 記一個(gè)指針從大到小掃右邊的.

[數(shù)學(xué) 分治]