algorithm - Josephus for large n(Facebook 黑客杯)

Question

上周我参加了 Facebook 黑客杯的第 1b 轮比赛。

问题之一基本上是 Josephus problem

我之前把约瑟夫斯问题当成离散数学问题研究过，所以我基本上明白了如何得到递归:

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

但这在 Facebook 黑客杯中不起作用，因为 n 的最大值为 10^12。 k 的 mak 值为 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 论坛上找到任何信息)

Answer 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 添加到结果中将得到我们的原始索引。