Random Analysis: Probabilities¶
Estimated time limit: 0.5 seconds. Memory limit: 128 MB.
On the target judge, multiply the reference program's largest per-case median time by \(2\) and round up to a multiple of \(0.5\) seconds. See the reference environment.
Story¶
A laboratory shuffles numbered cards using random swaps in a fixed order. A researcher wants to determine the final value distribution at each position.
(This story was rewritten by GPT-6.)
Formal Problem Statement¶
Given an integer sequence \(a_1,\ldots,a_n\) indexed from \(1\) , perform the following operations on the current sequence. Values may repeat.
for i = 1, 2, ..., n:
r = uniformly_random_integer(1, n)
swap(a[i], a[r])
Each random choice is independent and uniform over all integers from \(1\) to \(n\) , including \(i\) . Each swap immediately changes the sequence used by subsequent rounds. Let the final sequence be \(A_1,\ldots,A_n\) .
Find the full matrix \(P_{i,j}=\Pr(A_i=j)\) for \(1\le i,j\le n\) . Rows represent positions and columns represent values. Distinct elements with the same value contribute to the same column; an absent value has a zero column.
Represent results modulo \(M=998244353\) : for a nonnegative rational result \(p/q\) with \(q>0\) , print the representative of \(p\cdot q^{-1}\bmod M\) in \([0,M-1]\) . Print \(0\) for a zero result. The constraints ensure that the required denominators are invertible modulo \(M\) .
Input Format¶
The first line contains \(n\) . The second line contains \(n\) integers \(a_1,\ldots,a_n\) .
Output Format¶
Print \(n\) lines of \(n\) integers. Entry \(j\) in line \(i\) represents \(P_{i,j}\) modulo \(M\) .
Examples¶
Example 1¶
Input¶
1
1
Output¶
1
Example 2¶
Input¶
3
1 2 3
Output¶
332748118 813384288 850356301
332748118 850356301 813384288
332748118 332748118 332748118
Example 3¶
Input¶
3
1 1 3
Output¶
147888053 0 850356301
184860066 0 813384288
665496236 0 332748118
Example Explanation¶
There are \(3^3=27\) equally likely sequences of random choices in the second example. Counting final outcomes gives the numerator matrix below, with denominator \(27\) in every cell. In the third example, both elements of value \(1\) contribute to the first column, while the second column is zero.
Rows are final positions and columns are values. Divide each count by \(27\) to obtain its probability.
Constraints and Guarantees¶
All inputs satisfy \(1\le n\le300\) and \(1\le a_i\le n\) .
Codex (GPT-6) specifies the size bound \(n\le300\) for this edition; the element range is \(1\le a_i\le n\) .
| Score | Additional conditions |
|---|---|
| 100% | None |