To co jak robiło się te kostki? Muszę przyznać zadania wczytaj trzy liczby policz coś modulo to moje ulubione

Skupiając się tylko na jednym graczu:
dp[x] = prawdopodobieństwo, że ten jeden gracz w trakcie rozgrywki stanie na wartości dokładnie x
Takiego dynamika można bezpośrednio obliczyć w O(m * k) lub odrobinę sprytniej w O(m).

above[x] = prawdopodobieństwo, że ten jeden gracz w trakcie rozgrywki stanie na jakiejś wartości z przedziału [x, m-1]
Takiego dynamika można bezpośrednio obliczyć w O(m * k * k) korzystając z dp lub odrobinę sprytniej również w O(m).

W treści jest powiedziane, że jeśli wiele graczy ma najmniejszą liczbę punktów, to rusza się losowy. Natomiast dla ułatwienia przyjmijmy, że rusza się ten o najmniejszym numerze (nie losowy). Nie zmienia to wyniku. Wynikiem będzie E[suma po X_(x,i) gdzie x=0...m-1, i=0...n-1] a zmienna X_(x,i) przyjmuje wartość 1 jeśli gracz nr i w trakcie rozgrywki wykonał ruch stojąc na wartości x, lub 0 w przeciwnym przypadku. Więc trzeba posumować prawdopodobieństwa X_(x,i) = 1.

P(X_(x,i) = 1) = dp[x] * above[x+1]^i * above[x]^(n-1-i)

dp[x] - prawdopodobieństwo, że ten gracz stanie na x.
above[x+1]^i - prawdopodobieństwo, że gracze o numerach mniejszych niż i staną kiedyś na wartości z przedziału [x+1,m-1], pozwalając graczowi i się ruszyć z wartości x.
above[x]^(n-1-i) - prawdopodobieństwo, że gracze o numerach większych niż i staną kiedyś na wartości z przedziału [x,m-1], pozwalając graczowi i się ruszyć z wartości x.

Te prawdopodobieństwa też można posumować w O(m * log(n)).

kropka w kropkę, jakby wyszedł z fabryki

A jednak nie, ja je sumuję w O(m*log(n)) - robisz bez loga Marek, czy to skrót myślowy?

Korzystam z faktu, że n <= 10^6, więc O(m * log(n)) = O(m).