Описание: В кругу стоят люди, ожидающие казни. Отсчет начинается в некоторой точке круга и продолжается по кругу в фиксированном направлении. На каждом шаге пропускается определенное количество людей и выполняется следующий человек. Исключение происходит по кругу (который становится все меньше и меньше по мере удаления казненных людей), пока не останется только последний человек, которому предоставлена свобода.

Я погуглил эту «проблему Иосифа», и хит из Википедии дает мне решение для динамического программирования:f(n,k)=((f(n-1,k)+k-1) mod n)+1, with f(1,k)=1, но это только дает последнего выжившего. Как я могу получить последовательность людей казненных? Скажем, p (5, 3) = {3,1,5,2,4}.

Кроме того, есть лиO(nlogn) решение вместоO(nk) один?