## A Math Contest P15 - Matrix Fixed Point

View as PDF

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

Authors:
Problem type

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

For this problem, input and output will be done modulo . This means that if is some fraction where , then you're given the integer modulo (and the same is true for output).

#### Constraints

Each column of sums to exactly .

#### Input Specification

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

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

#### Output Specification

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

#### Sample Input

2
900000007 500000004
100000001 500000004

#### Sample Output

625000005 375000003

#### Explanation for Sample

We are given the transition matrix of

and find that its steady-state vector is .