今天还算挺有收获，首先，终于第一次见到了怎样用随机搜索来过NP难问题，多谢晓鸣详细而生动的分析
。
下午看了那份月赛的简单题解之后对那题PM3豁然开朗。(虽然对Rescue Alice还是完全不明白...）
http://acm.pku.edu.cn/JudgeOnline/problem?id=3213
Problem D: PM3
Let E = {1}1 × N, F = {1}M × 1. C = AB implies EC = E(AB) and CF = (AB)F. If C and AB differ at the element in row r and column c, then EC and E(AB) will differ at the element in column c, and CF and (AB)F will differ at the element in row r. Thus the incorrect element of C can be located by evaluating and comparing EC, E(AB), CF and (AB)F. Exploiting the associativity of matrix multiplication, E(AB) and (AB)F can be first changed into (EA)B and A(BF) before evaluation, which can lead to a great speed-up.
原来O(n3)可以这么巧妙地化为O(n2)。唉，线性代数没学好啊。按照提示，很快就把题目做了出来。看着整整齐齐的一版代码，突然兴起了写一份解题报告的念头，算是一个自我总结，也是和队员和其他acm初学者们交流吧。望各位大牛勿笑。
看完题后，先看数据规模，1000，不是很大，可是如果用标准的矩阵计算方法，M*N*P的规模，就变成109
了。这是不可接受的。一般题目能接受的复杂度就只到108。于是就要找降低复杂度的方法，如上提示所述。要注意的一个小地方是，存储矩阵的数组不能设为int的，因为虽然它说矩阵A、B的元素绝对值不超过1000，可是在计算乘法时就肯定会超过int的范围了，矩阵C的提示也说‘小于2*109’，可是还是有些人粗心地用了int，包括discuss里叫着WA的人和我的队友。至于内存这里就不用担心了。Memory Limit:131072K，也就是说131072*1024字节，开3个1001*1001*4字节的long数组，6个1001*4的long数组，也只是4000多K，不会超。
附：复习一下---整数类型范围，应该牢记
| int |
2字节 |
-32768 ~ 32767 |
| unsigned int |
2字节 |
0 ~ 65535 |
| long |
4字节 |
约-2*109 ~ 2*109 |
| unsigned long |
4字节 |
0 ~约 4*109 |
| __int64 |
8字节 |
约9*1018 |
| unsigned __int64 |
8字节 |
约1.8*1019 |