Random Analysis: Expectations¶
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 expected final value 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 expected value \(E_i=\mathbb{E}[A_i]\) at every position.
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 one line of \(n\) integers. The \(i\)-th integer represents \(E_i\) modulo \(M\) .
Examples¶
Example 1¶
Input¶
1
1
Output¶
1
Example 2¶
Input¶
3
1 2 3
Output¶
517608185 480636172 2
Example 3¶
Input¶
3
1 1 3
Output¶
702468250 628524224 665496237
Example Explanation¶
The actual expectations in the second example are \(53/27,55/27,2\) , so they are not all equal to the mean. The third example has two elements of value \(1\) ; its expectations are \(43/27,47/27,5/3\) . The output converts these fractions to modular representatives.
The diagram shows the second example. 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 |