Джозефус для большого n (Кубок Hacker Facebook)

На прошлой неделе я участвовал в раунде 1b кубка Facebook Hacker.

Одна из проблем заключалась в основном в проблеме Josephus

Я изучил проблему Иосифа Флавия раньше как дискретную математическую задачу, поэтому я в основном понимаю, как получить повторение:

f(n,k) = (f(n-1,k) + k) mod n, with f(1,k) = 0

Но это не сработало в Facebook Hacker Cup, потому что максимальное значение n было 10 ^ 12. Значение mak k составляло 10 ^ 4.

Википедия упоминает подход, когда k мало и n велико. В основном удалите людей из одного раунда, а затем перенумеруйте. Но это не описано много, и я не понимаю, почему работает перенумеровка.

Я рассмотрел образец рабочего исходного кода для решения, но я до сих пор не понимаю эту заключительную часть.

long long joseph (long long n,long long k) {
    if (n==1LL) return 0LL;
    if (k==1LL) return n-1LL;
    if (k>n) return (joseph(n-1LL,k)+k)%n;
    long long cnt=n/k;
    long long res=joseph(n-cnt,k);
    res-=n%k;
    if (res<0LL) res+=n;
    else res+=res/(k-1LL);
    return res;
}

Часть, которую я действительно не понимаю, начинается с res-=n%k (и последующих строк). Как вы узнаете, что это способ настроить результат?

Может ли кто-нибудь показать рассуждения о том, как это происходит? Или ссылку, которая его выводит? (Я не нашел информации о форумах UVA или topcoder)

Ответы

Ответ 1

Правильно, я думаю, что я его взломал.

Посмотрим, как идут итерации с n = 10, k = 3:

0 1 2 3 4 5 6 7 8 9    n=10,k=3
1 2   3 4   5 6   0    n=7,k=3

Наблюдайте, как элементы второй итерационной карты относятся к первой: они транспонируются на n%k, потому что круг обертывается вокруг. Поэтому мы исправим результат, вычитая 10%3. Цифры во второй строке появляются в группах k-1, поэтому исправление res/(k-1).

Другой случай ударяется дальше по итерациям

0 1 2 3 4     n=5,k=3
2 3   0 1     n=4,k=3

Теперь j (4,3) возвращает 0, что исправлено 5%3, оказывается равным -2. Это происходит только в том случае, если результат второй строки находится в последней группе, и в этом случае добавление n к результату даст нам наш исходный индекс.