A Math Contest P15 - Matrix Fixed Point

View as PDF

Submit solution

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

Problem type

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

  • Pv = v
  • 0 \le v_1, \dots, v_N \le 1
  • \sum_{i=1}^N v_i = 1

For this problem, input and output will be done modulo 10^9 + 7. This means that if P_{ij} is some fraction A/B where 0 < A \le B, then you're given the integer A \cdot B^{-1} modulo 10^9 + 7 (and the same is true for output).


1 \le N \le 500

0 < P_{ij} \le 1

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 P_{ij}.

Output Specification

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

Sample Input

900000007 500000004
100000001 500000004

Sample Output

625000005 375000003

Explanation for Sample

We are given the transition matrix of

\displaystyle P=\begin{bmatrix}7/10 & 1/2 \\ 3/10 & 1/2\end{bmatrix}

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


There are no comments at the moment.