Probability of Final Position after Random Swaps

We are given a sequence \(a\) of length \(n\) where initially \(a_i=i\) for \(1\le i\le n\). We also have a random integer \(x\) in \([1,n]\) such that \(x=i\) with probability \(b_i\) (\(\sum_{i=1}^{n}b_i=1\)). Then, we perform \(k\) operations. In each operation, two indices \(i,j\) are chosen uniformly at random from \([1,n]\) (it is allowed that \(i=j\)); then the values \(a_i\) and \(a_j\) are swapped (if \(i=j\) nothing happens).

Your task is to compute for each \(1\le i\le n\) the probability that after all operations \(x\) ends up in position \(i\) (that is, \(a_i=x\)). Output your answers modulo \(3221225473\). All formulas should be given in \(\LaTeX\) format.

Analysis:

Initially, since \(x=i\) with probability \(b_i\) and the permutation is the identity, the element \(x\) starts from position \(i\) if \(x=i\). Each swap is done by choosing two indices uniformly and swapping the elements. If we track the position of a fixed element, notice that in one swap, if the element is at position \(r\), then:

[ P(r \to r) = \frac{(n-1)^2+1}{n^2} = \frac{n^2-2n+2}{n^2}, \quad \text{and} \quad P(r \to s) = \frac{2}{n^2} \quad (s\neq r). ]

This Markov chain is of the form \(P = \alpha I + \beta (J-I)\) with \(\alpha = \frac{n^2-2n+2}{n^2}\) and \(\beta = \frac{2}{n^2}\). Its eigenvalues are \(1\) (with multiplicity 1) and \(\lambda = \alpha-\beta = \frac{n-2}{n}\) (with multiplicity \(n-1\)). Thus, the transition probability (after \(k\) operations) from position \(j\) to \(i\) is

[ P_k(i\mid j)= \frac{1}{n} + \Bigl(\delta_{ij}-\frac{1}{n}\Bigr) \Bigl(\frac{n-2}{n}\Bigr)^k. ]

Since \(x\) starts at position \(j\) with probability \(b_j\), the final probability for position \(i\) is

[ ans_i = \frac{1}{n} + \Bigl(\frac{n-2}{n}\Bigr)^k\Bigl(b_i-\frac{1}{n}\Bigr). ]

All computations are to be done modulo \(M = 3221225473\). In modular arithmetic, division by \(n\) is performed by multiplying with the modular inverse \(n^{-1}\) modulo \(M\). In particular, note that

[ \Bigl(\frac{n-2}{n}\Bigr)^k = (n-2)^k \cdot (n^{-1})^k \pmod{M}. ]

inputFormat

The first line contains two integers \(n\) and \(k\) (\(1 \le n \le 10^5\), \(0 \le k \le 10^9\)).

The second line contains \(n\) integers \(b_1, b_2, \ldots, b_n\). It is guaranteed that \(\sum_{i=1}^n b_i=1\); you may assume that the \(b_i\)'s are given in a format allowing exact arithmetic modulo \(3221225473\) (for example, as integers representing probabilities modulo \(3221225473\)).

outputFormat

Output \(n\) integers, where the \(i\)-th integer is the probability that \(x\) ends up at position \(i\) (i.e. \(a_i=x\)) modulo \(3221225473\).

sample

3 0
1 0 0

1 0 0