500pt Perfect Memory
题意: 某神在M*N(1<=M, N<=50, M*N为偶数)的格子上玩对对碰: 每个格子都有个隐藏的图形. 此神一次行动翻开2个, 如果相同, 就成功消去这2个格子. 如果不相同, 那这2个格子又恢复隐藏状态. 但是此神记忆力很NB, 能记住所有翻开过的格子是什么图形. 还有重要的一点, 他一次行动时, 是先翻开1个格子, 知道它的图形之后, 再决定怎么翻第2个格子, 而不是两个格子同时翻开. 问此神把所有格子都消去, 需要消耗的行动次数的期望.

容易想到期望与翻格子的位置无关. 有关的量是: 当前还有多少对图形没被消去. 其中有多少对图形已经知道其中一个的位置了. so, dp[i][j], i为前者, j为后者. 一次行动中, 第1个格子肯定翻之前没翻过的(一共有2i-j个, 记为s), 除非已经知道某1对的位置, 直接把2个都翻出来消掉. 所以转移有几种情况:
1) 从s中翻出1个新图形. 从剩下s-1中翻出了相同图形, 消除. 这样的概率是2(i-j)/s * 1/(s-1), 转移到dp[i-1][j].
2) 从s中翻出1个新图形. 从剩下s-1中又翻出新图形, 这样就多了2种已知图形. 概率是2(i-j)/s * 2(i-j-1)/(s-1), 转移到dp[i][j+2].
3) 从s中翻出1个新图形. 从剩下s-1中翻出了之前j个已知图形中的一个. 这样, 下一次就可以消耗一次行动把那对已知图形消去, 转移到dp[i-1][j], 概率是2(i-j)/s * j/(s-1).
4) 从s中翻出1个已知图形. 直接翻出与它配对的消去. 转移到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)处出发, 想去(X,Y,Z)处. 现在他每行动一次可以做如下移动:
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) 神一次行动可以利用一个平面, 移动到关于这个平面对称的点处. 每个平面在整个游戏过程中至多只能利用一次.
问此神到达终点花费的最少行动次数.

易知三个方向是不相关的. 所以只用先考虑一维的情形.
首先要想到, 走路和反射交替, 是等效于先反射完了再一口气走到终点的. 因为在反射之前的走动, 不会被反射动作放大. 反射前移动多少步, 经过若干次反射后所到达的位置, 与不移动直接反射到达的位置, 相差正好是移动的步数.
所以可以转化为先反射若干次, 再行走到终点. 现在就要推出反射到达的位置公式.
假设每个反射轴的坐标依次是x[1], x[2], ..., x[n], 神经过第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].
这是很规则的正负交替求和, 正项数等于负项数, 或者比负项数多1.
到此问题转化得很清晰了: 在20个数中选出k个数作为正项, k(或k-1)个数作为负项, 每个数至多被选1次. 该方案的总行动次数是选出的个数(即做反射的总次数), 加上这些项之和到终点的距离(即最后一路走过去). 
选数要降低复杂度, 可以把20个数分成两个集合, 每边10个数, 先各自生成2^10个和. 两边分别排序后, 从小到大枚举左边的, 记一个指针从大到小扫右边的.

[数学 分治]