import sys # Get the matrix into the form: # Q R # 0 I # and then return the first row of ((I-Q)^-1)R # because markov chains are magic and solve the infinite sum for you from fractions import * class Matrix: def __init__(self, height, width): self.rows = height self.cols = width self.m = [[0 for i in range(height)] for j in range(width)] def minor(self, r, c): result = Matrix(self.rows - 1, self.cols - 1) result.m = [row[:] for row in self.m] del result.m[r] for row in result.m: del row[c] return result def cofactor(self, r, c): return (self.m[r][c] * (1 if (r + c) % 2 == 0 else -1) * self.minor(r, c).det()) def det(self): if self.rows == 2: return self.m[0][0] * self.m[1][1] - self.m[1][0] * self.m[0][1] return sum(self.cofactor(0, i) for i in range(self.cols)) def adjoint(self): result = Matrix(self.rows, self.cols) result.m = [row[:] for row in self.m] for i in range(result.rows): for j in range(i + 1, result.cols): result.m[i][j], result.m[j][i] = result.m[j][i], result.m[i][j] return result def inverse(self): det = self.det() if self.rows == 2: result = Matrix(2, 2) result.m[0][0] = self.m[1][1] / det result.m[1][0] = -self.m[1][0] / det result.m[0][1] = -self.m[0][1] / det result.m[1][1] = self.m[0][0] / det return result temp = Matrix(self.rows, self.cols) temp.m = [row[:] for row in self.m] for i in range(temp.rows): for j in range(temp.cols): temp.m[i][j] = (self.minor(i, j).det() * -(((i + j) % 2) * 2 - 1)) temp = temp.adjoint() for i in range(temp.rows): for j in range(temp.cols): temp.m[i][j] /= det return temp def __sub__(self, other): result = Matrix(self.rows, self.cols) for i in range(self.rows): for j in range(self.cols): result.m[i][j] = self.m[i][j] - other.m[i][j] return result def __mul__(self, other): result = Matrix(other.cols, self.rows) for i in range(result.cols): for j in range(result.rows): dot = 0 for k in range(self.cols): dot += self.m[i][k] * other.m[k][j] result.m[i][j] = dot return result def __str__(self): return '\n'.join( [' '.join(["{0:>3}".format(i) for i in row]) for row in self.m]) def identity(size): result = Matrix(size, size) for i in range(size): result.m[i][i] = 1 return result def answer(m): if len(m) <= 2: return [1, 1] fixed = [m[0]] front = 1 for i in range(1, len(m)): if any(m[i]): fixed.append(m[i]) while i > front: for row in m: row[i], row[i - 1] = row[i - 1], row[i] i -= 1 front += 1 m = fixed for row in m: temp = sum(row) for i in range(len(row)): row[i] = Fraction(row[i]) / temp size = len(m) q = Matrix(size, size) q.m = [row[:size] for row in m[:size]] r = Matrix(size, len(m[0]) - size) r.m = [row[size:] for row in m[:size]] i = identity(size) # print "Q" # print q # print "R" # print r # print "I" # print i # print "I-Q" # print i - q # print "(I-Q)^-1" # print (i - q).inverse() # print "(I-Q)^-1 * r" # print (i - q).inverse() * r ans = r if q.rows == 1 else (i - q).inverse() * r total_gcd = reduce((lambda x, y: gcd(x, y)), ans.m[0]) return [int(n / total_gcd) for n in ans.m[0]] + [total_gcd.denominator] # a = Matrix(3, 3) # a.m = [[3., 0., 2.], [2., 0., -2.], [0., 1., 1.]] # a.m = [[Fraction(i) for i in row] for row in a.m] # a = a.inverse() # print "Final:" # print a # print "Identity" # print identity(3) # a = Matrix(2, 3) # a.m = [[1, 2, 3], [4, 5, 6]] # b = Matrix(3, 2) # b.m = [[7, 8], [9, 10], [11, 12]] # print a # print # print b # print # print a * b # sys.exit() test1 = [[0, 2, 1, 0, 0], [0, 0, 0, 3, 4], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0]] sol1 = [7, 6, 8, 21] test2 = [[0, 1, 0, 0, 0, 1], [4, 0, 0, 3, 2, 0], [0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0]] sol2 = [0, 3, 2, 9, 14] test3 = [[2, 3, 1, 1, 0, 1], [0, 0, 0, 0, 0, 0], [4, 1, 0, 3, 2, 0], [2, 3, 0, 1, 3, 0], [0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0]] test4 = [ [0, 1, 0, 0, 0, 1, 2, 3, 2, 1], [4, 0, 0, 3, 2, 0, 9, 2, 2, 3], [1, 0, 0, 1, 0, 0, 0, 0, 0, 0], [0, 1, 0, 0, 1, 0, 0, 0, 0, 0], [0, 1, 0, 0, 0, 0, 0, 2, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 3, 0, 0, 0, 0, 0], [0, 0, 4, 0, 0, 3, 0, 0, 0, 0], [0, 0, 0, 0, 0, 10, 2, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], ] test5 = [[1, 2, 3, 0, 0, 0], [4, 5, 6, 0, 0, 0], [7, 8, 9, 1, 0, 0], [0, 0, 0, 0, 1, 2], [0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0]] print answer(test1) print answer(test2) assert ( answer([ [0, 2, 1, 0, 0], [0, 0, 0, 3, 4], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0] ]) == [7, 6, 8, 21] ) assert ( answer([ [0, 1, 0, 0, 0, 1], [4, 0, 0, 3, 2, 0], [0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0] ]) == [0, 3, 2, 9, 14] ) assert ( answer([ [1, 2, 3, 0, 0, 0], [4, 5, 6, 0, 0, 0], [7, 8, 9, 1, 0, 0], [0, 0, 0, 0, 1, 2], [0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0] ]) == [1, 2, 3] ) assert ( answer([ [0] ]) == [1, 1] ) assert ( answer([ [0, 0, 12, 0, 15, 0, 0, 0, 1, 8], [0, 0, 60, 0, 0, 7, 13, 0, 0, 0], [0, 15, 0, 8, 7, 0, 0, 1, 9, 0], [23, 0, 0, 0, 0, 1, 0, 0, 0, 0], [37, 35, 0, 0, 0, 0, 3, 21, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0] ]) == [1, 2, 3, 4, 5, 15] ) assert ( answer([ [0, 7, 0, 17, 0, 1, 0, 5, 0, 2], [0, 0, 29, 0, 28, 0, 3, 0, 16, 0], [0, 3, 0, 0, 0, 1, 0, 0, 0, 0], [48, 0, 3, 0, 0, 0, 17, 0, 0, 0], [0, 6, 0, 0, 0, 1, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]) == [4, 5, 5, 4, 2, 20] ) assert ( answer([ [1, 1, 1, 1, 1, 1, 1, 1, 1, 1], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0] ]) == [1, 1, 1, 1, 1, 5] ) assert ( answer([ [1, 1, 1, 0, 1, 0, 1, 0, 1, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [1, 0, 1, 1, 1, 0, 1, 0, 1, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [1, 0, 1, 0, 1, 1, 1, 0, 1, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [1, 0, 1, 0, 1, 0, 1, 1, 1, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [1, 0, 1, 0, 1, 0, 1, 0, 1, 1], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0] ]) == [2, 1, 1, 1, 1, 6] ) assert ( answer([ [0, 86, 61, 189, 0, 18, 12, 33, 66, 39], [0, 0, 2, 0, 0, 1, 0, 0, 0, 0], [15, 187, 0, 0, 18, 23, 0, 0, 0, 0], [1, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0] ]) == [6, 44, 4, 11, 22, 13, 100] ) assert ( answer([ [0, 0, 0, 0, 3, 5, 0, 0, 0, 2], [0, 0, 4, 0, 0, 0, 1, 0, 0, 0], [0, 0, 0, 4, 4, 0, 0, 0, 1, 1], [13, 0, 0, 0, 0, 0, 2, 0, 0, 0], [0, 1, 8, 7, 0, 0, 0, 1, 3, 0], [1, 7, 0, 0, 0, 0, 0, 2, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0] ]) == [1, 1, 1, 2, 5] )