Hall of Songs#13109

Hall of Songs (Editorial)

By linearity of expectation, the answer is the sum over the initial songs of the probability that the song is still known after evenings. All songs are symmetric, so the answer is n \cdot s, where is the probability that one fixed song survives.

Follow that song and let be the number of musicians who know it; initially c = 1. An evening changes only if exactly one of and knows the song. If knows it and does not, grows by one; if knows it and does not, drops by one. Each of the two events has probability

r_c = \frac{c\,(n-c)}{n\,(n-1)},

and with probability 1 - 2r_c nothing changes. The next value of depends only on the current one, so is a Markov chain on the states 0, 1, \ldots, n, and the song is lost for good exactly when reaches (then r_0 = 0).

Let be the (n+1) \times (n+1) transition matrix of this chain: T_{c,c-1} = T_{c,c+1} = r_c and T_{c,c} = 1 - 2r_c. The distribution of after evenings is the row of T^k, hence

\text{answer} = n \cdot \bigl(1 - (T^k)_{1,0}\bigr).

All computations can be done directly modulo M = 998\,244\,353: the probabilities r_c become c(n-c) \cdot (n(n-1))^{-1} \bmod M, and the matrix power uses only additions and multiplications, so the result is the required residue p \cdot q^{-1} \bmod M. Compute T^k by binary exponentiation: at most 2 \log_2 k \approx 120 multiplications of matrices of size at most 101 \times 101. Note that needs a 64-bit type. It must not be reduced modulo M - 1: is singular, so Fermat's little theorem does not apply to it.

The complexity is O(n^3 \log k).

Remark. Looking backwards in time, the ancestral lines of the musicians merge like in Kingman's coalescent, which leads to a closed form computable in O(n \log k); it is not needed here.