bon

PKU 2941
這道題需要?jiǎng)右幌履X筋，屬于數(shù)學(xué)題。
問(wèn)題描述：給一個(gè)n×n的矩陣，如果從每行各拿出一個(gè)元素，且這些元素的列指標(biāo)都不同，即



其中是的一個(gè)排列。
如果任何這樣一個(gè)元素的和都相等，則稱(chēng)這個(gè)矩陣是homogeneous的。

題目要求任給一個(gè)n維矩陣,1<=n<=1000，判斷它是否是homogeneous的。

如果直接做，即求出所有的然后求和，這樣的復(fù)雜度為n!，這是無(wú)法接受的。

下面給出一個(gè)算法，能在時(shí)間內(nèi)判斷出來(lái)。設(shè)n維矩陣A，現(xiàn)為A加上一行跟一列，使A變成n+1維的。



Theorem 1 

若n維矩陣A是homogeneous的，則劃去A的任一行與任一列，剩下的n-1維矩陣是homogeneous的。

Proof
設(shè)劃去的是第x行第y列，剩下的矩陣若不是homogeneous的，則存在與，這兩個(gè)序列的和不等，那么都加上，可以得到矩陣A的兩個(gè)序列，這兩個(gè)序列的和不等，即A不是homogeneous的，與假設(shè)矛盾。

Theorem 2
若Homogeneous的A增廣后的矩陣B是Homogeneous的，則對(duì)于A中任意元素 ，必有

Proof
這個(gè)等式的意義是在A取元素，在新矩陣取，其余任取，這么一個(gè)序列的和必須等于在新矩陣中取跟，其余任取所得的序列的和。注意到任取那部分是在A劃去行i，列j后的子矩陣中取的。由于B是Homogeneous，任何合法序列的和都相等，若題設(shè)的等式不成立，則任取這一部分也不相等（這樣才可能使得所有B包含的序列的和都相等）。但A是Homogeneous的，任取這一部分不可能不等，矛盾。

有了上面的定理2，算法就很簡(jiǎn)單，看下面的代碼：