Раскрасим вершины в 3 цвета: черные, белые в четных строках — назовем "красные", и белые в нечетных строках — назовем "синие". Тогда каждая тройка содержит ровно одну каждого цвета. Теперь понятно какой поток: из истока в красные в черные в синие в сток, с ограничением на пропускную способность вершин.

Рандомный просмотр history топов, у кого 500 попадала, показывает, что у всех упал этот тест: (под катом)

Лишь бы не сделали unrated...

Ух ты, это может запросто вызвать рантайм в моем решении.

У меня как раз этот тест упал по Exception.

Если мы в нечетной, то второй выигрывает просто повторяя ходы первого. Дальше почти из всех чётных можно пойти в нечётную, значит там первый выигрывает. Остались степени двойки. Если у нас 2^n, то после вычитания чего угодно кроме 2^{n-1} можно пойти в нечетное, поэтому первый так делать не будет и вычтет 2^{n-1}, то есть просто поделит на два.

Для каждого элемента строки посчитаем, во сколько подстрок он входит (по формуле). А ещё посчитаем вероятность, с которой любой элемент после K ходов останется на месте. Это линейная динамика p[i] считается через p[i-1]. После этого для каждого элемента val[i] его значение — это p[k] * val[i] + (1 — p[k]) * (sum — val[i])/(n-1). Предоставим читателю самостоятельно додумать тонкости реализации.

Например, так: считаем вероятность, что после k шагов на данном фиксированном месте останется то же число, что стояло в самом начале. Это можно сделать за O(k) или за O(log(k)). Дальше всё просто — если в конце на данной позиции стоит какое-то другое число, то вероятность того, что это за число, распределена пропорционально количеству этого числа в последовательности. Поэтому для каждой пары (позиция, число) мы знаем вероятность, а значит, ответ — это понятно какая сумма по линейности матожидания.