Flawiusz za duże n (Facebook Hacker Cup)

Question

W zeszłym tygodniu uczestniczyłem w rundzie 1b na Facebooku Hackers Cup.

Jednym z problemów było w zasadzie Josephus problem

Uczyłem problem Józef wcześniej jako dyskretny problem matematyczny, więc ja po prostu zrozumieć, jak uzyskać nawrotom:

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

ale nie zrobił pracują w Puchar Hackera Facebooka, ponieważ maksymalna wartość n wynosi 10^12. Wartość mak k wynosi 10^4.

Wikipedia wspomina o podejściu, gdy k jest małe, a n jest duże. Zasadniczo usuń ludzi z jednej rundy, a następnie ponumeruj. Ale to nie jest opisane wiele i nie rozumiem, dlaczego numeracja działa.

Sprawdziłem przykładowy kod źródłowy rozwiązania, ale nadal nie rozumiem tej ostatniej części.

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; 
} 

Część I naprawdę nie rozumiem, począwszy od res-=n%k (a linie później). Jak wywnioskować, że jest to sposób na dostosowanie wyniku?

Czy ktoś może przedstawić uzasadnienie tego, w jaki sposób się wywodzi? Lub link, który go wyprowadza? (Nie znalazłem żadnych informacji na temat forów UVA lub topcoder)

Answer 1

Dobra, myślę, że to załamałem. wygląd

Miejmy w jaki sposób iteracji iść z 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 

obserwować, jak elementy drugiej iteracji mapy, aby pierwsza: są transponowane przez n%k, ponieważ koła owija się wokół. Właśnie dlatego poprawiamy wynik przez odjęcie 10%3. Liczby w drugim rzędzie pojawiają się w grupach k-1, stąd korekta o res/(k-1).

Drugi przypadek jest trafiony dalej wzdłuż iteracji

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

Teraz j (4,3) zwraca 0, które rozwiązane przez 5%3 okazuje się być -2. Dzieje się tak tylko wtedy, gdy wynik drugiego wiersza znajduje się w ostatniej grupie, w którym to przypadku dodanie do wyniku n da nam nasz oryginalny indeks.