A Math Contest P15 - Matrix Fixed Point

View as PDF

Submit solution


Points: 20
Time limit: 1.0s
Memory limit: 512M

Authors:
Problem type

You are given the N×N transition matrix for a regular Markov chain, and you need to find its steady state vector. Formally, given an N×N matrix P, you need to find the unique vector v such that

  • Pv=v
  • 0v1,,vN1
  • i=1Nvi=1

For this problem, input and output will be done modulo 109+7. This means that if Pij is some fraction A/B where 0<AB, then you're given the integer AB1 modulo 109+7 (and the same is true for output).

Constraints

1N500

0<Pij1

Each column of P sums to exactly 1.

Input Specification

The first line contains an integer, N, the number of possible events to consider.

The next N lines contain N space-separated numbers, representing the matrix P (as defined above). The j-th integer on the i-th row contains Pij.

Output Specification

Output N space-separated numbers, the entries of the unique vector v.

Sample Input

Copy
2
900000007 500000004
100000001 500000004

Sample Output

Copy
625000005 375000003

Explanation for Sample

We are given the transition matrix of

P=[7/101/23/101/2]

and find that its steady-state vector is v=5/8,3/8.


Comments

There are no comments at the moment.