Josephus cho lớn n (Facebook Hacker Cup)

Question

Tuần trước tôi đã tham gia vòng 1b của Facebook Hacker cup.

Một trong những vấn đề căn bản vẫn là Josephus problem

Tôi đã nghiên cứu vấn đề Josephus trước khi là một vấn đề toán học rời rạc, vì vậy tôi về cơ bản hiểu làm thế nào để có được sự tái phát:

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

Nhưng didn rằng 't làm việc trong Facebook Hacker Cup, bởi vì giá trị tối đa của n là 10^12. Giá trị mak của k là 10^4.

Wikipedia đề cập đến cách tiếp cận khi k nhỏ và n lớn. Về cơ bản loại bỏ những người từ một vòng duy nhất, và sau đó renumber. Nhưng nó không được mô tả nhiều và tôi không hiểu tại sao các công trình renumbering lại.

Tôi đã xem mã nguồn mẫu làm việc cho giải pháp, nhưng tôi vẫn không hiểu phần cuối cùng đó.

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

Phần tôi thực sự không hiểu là bắt đầu từ res-=n%k (và các dòng sau đó). Làm thế nào để bạn nhận ra rằng đó là cách để điều chỉnh kết quả?

Ai đó có thể cho biết lý do đằng sau cách bắt nguồn này? Hoặc một liên kết xuất phát từ nó? (Tôi không tìm thấy bất kỳ thông tin nào về diễn đàn UVA hoặc topcoder)

Answer 1

Phải, tôi nghĩ tôi đã bẻ khóa.

Hãy nhìn vào cách lặp đi với 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 

Quan sát cách các yếu tố của bản đồ thứ hai lặp để là người đầu tiên một: họ đang hoán bởi n%k, vì vòng tròn bao bọc xung quanh. Đó là lý do tại sao chúng tôi sửa kết quả bằng cách trừ 10%3. Các số trong hàng thứ hai xuất hiện trong các nhóm k-1, do đó hiệu chỉnh theo res/(k-1).

Các trường hợp khác được nhấn thêm dọc theo lặp

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

Bây giờ j (4,3) trả về 0, trong đó điều chỉnh bởi 5%3 hóa ra là -2. Điều này chỉ xảy ra nếu kết quả của hàng thứ hai nằm trong nhóm cuối cùng, trong trường hợp này thêm n vào kết quả sẽ cung cấp cho chúng tôi chỉ mục ban đầu của chúng tôi.