bon

PKU 2941
这道题需要动一下脑筋，属于数学题。
问题描述：给一个n×n的矩阵，如果从每行各拿出一个元素，且这些元素的列指标都不同，即



其中是的一个排列。
如果任何这样一个元素的和都相等，则称这个矩阵是homogeneous的。

题目要求任给一个n维矩阵,1<=n<=1000，判断它是否是homogeneous的。

如果直接做，即求出所有的然后求和，这样的复杂度为n!，这是无法接受的。

下面给出一个算法，能在时间内判断出来。设n维矩阵A，现为A加上一行跟一列，使A变成n+1维的。



Theorem 1 

若n维矩阵A是homogeneous的，则划去A的任一行与任一列，剩下的n-1维矩阵是homogeneous的。

Proof
设划去的是第x行第y列，剩下的矩阵若不是homogeneous的，则存在与，这两个序列的和不等，那么都加上，可以得到矩阵A的两个序列，这两个序列的和不等，即A不是homogeneous的，与假设矛盾。

Theorem 2
若Homogeneous的A增广后的矩阵B是Homogeneous的，则对于A中任意元素 ，必有

Proof
这个等式的意义是在A取元素，在新矩阵取，其余任取，这么一个序列的和必须等于在新矩阵中取跟，其余任取所得的序列的和。注意到任取那部分是在A划去行i，列j后的子矩阵中取的。由于B是Homogeneous，任何合法序列的和都相等，若题设的等式不成立，则任取这一部分也不相等（这样才可能使得所有B包含的序列的和都相等）。但A是Homogeneous的，任取这一部分不可能不等，矛盾。

有了上面的定理2，算法就很简单，看下面的代码：