Monthly Archives: February 2011

SPOJ MATCH

好久不写blog了,写一道神题SPOJ MATCH的解题报告。

题意很简单,给定一个二分图,求其完美匹配的个数的奇偶性。二分图每侧最多300个点。

题解说来也很简单,但是本人实在智商不够,完全没想到点子上,经大神点拨才恍然大悟。

设二分图对应的邻接矩阵为A,也就是说,如果左边点i到右边点j有边,则A[i][j] = 1。完全匹配的个数实际上就是

match1

此处S表示所有[0..n-1]的排列,x表示其中的一个排列。

容易发现这个公式很类似于矩阵A的行列式

match2

这里inv(x)表示排列x的逆序数。唯一的区别在于(-1)^inv(x),但是在此题模2的意义下,正负号是不影响结果的。于是解法就是用高斯消元求邻接矩阵A的行列式值模2即可。复杂度O(n^3)。

此题有一个升级版CEPC 2009 Problem F. (False) Faces,是要求模4,貌似难了不少……