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

容易想到期望與翻格子的位置無關(guān). 有關(guān)的量是: 當(dāng)前還有多少對圖形沒被消去. 其中有多少對圖形已經(jīng)知道其中一個的位置了. so, dp[i][j], i為前者, j為后者. 一次行動中, 第1個格子肯定翻之前沒翻過的(一共有2i-j個, 記為s), 除非已經(jīng)知道某1對的位置, 直接把2個都翻出來消掉. 所以轉(zhuǎn)移有幾種情況:
1) 從s中翻出1個新圖形. 從剩下s-1中翻出了相同圖形, 消除. 這樣的概率是2(i-j)/s * 1/(s-1), 轉(zhuǎn)移到dp[i-1][j].
2) 從s中翻出1個新圖形. 從剩下s-1中又翻出新圖形, 這樣就多了2種已知圖形. 概率是2(i-j)/s * 2(i-j-1)/(s-1), 轉(zhuǎn)移到dp[i][j+2].
3) 從s中翻出1個新圖形. 從剩下s-1中翻出了之前j個已知圖形中的一個. 這樣, 下一次就可以消耗一次行動把那對已知圖形消去, 轉(zhuǎn)移到dp[i-1][j], 概率是2(i-j)/s * j/(s-1).
4) 從s中翻出1個已知圖形. 直接翻出與它配對的消去. 轉(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
題意: 某神在三維空間中玩一個游戲, 空間中有N個(N<=20)平面, 每個平面都垂直于某個坐標軸, 并且與該坐標軸交于整點. 此神從(0,0,0)處出發(fā), 想去(X,Y,Z)處. 現(xiàn)在他每行動一次可以做如下移動:
1) 走到與他相鄰的1個整點上, 即(x+1, y, z) (x-1, y, z) (x, y+1, z) (x, y-1, z) (x, y, z+1) (x, y, z-1)中的一個.
2) 神一次行動可以利用一個平面, 移動到關(guān)于這個平面對稱的點處. 每個平面在整個游戲過程中至多只能利用一次.
問此神到達終點花費的最少行動次數(shù).

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

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