====== 요세푸스 문제 ======
  * [[wp>Josephus problem]]과 [[https://cp-algorithms.com/others/josephus_problem.html]]을 참고하자.
  * 제외되는 번호를 순서대로 나열한 요세푸스 순열을 구하는 문제와, 마지막으로 제외되는 번호를 구하는 문제가 있다.
    * 1~n번까지 번호가 있을때, 매 k번째 번호를 제외시킨다

===== 요세푸스 순열을 모두 나열하기 =====
  * 그냥 하나씩 삭제하는 과정을 그대로 시뮬레이션을 해보면서 삭제되는 원소를 출력하는 식으로 구현한다.
  * k가 작을 때는 deque를 이용해서 시뮬레이션 한다. 맨 앞의 원소를 삭제하고, 그다음 k-1개의 원소를 맨 뒤로 rotate 시키는 것을 반복한다. 이러면 O(kn)에 처리할 수 있다.
  * k가 크면, x번째 원소를 삭제하고, 남은 원소중에서 (x + k - 1) % {남은 원소의 수} 번째 원소를 삭제하는 것을 반복하는 식으로 처리한다. x번째 원소를 찾고 삭제하는 것은, [[ps:Order Statistic Tree]]를 이용해서 O(logn)에 처리할 수 있다. 따라서 전체 시간복잡도는 O(nlogn)이 된다

==== 관련 문제 ====
  * [[ps:problems:boj:2161]] : k=2인 경우. deque 사용
  * [[ps:problems:boj:1168]] : k≤n≤100,000. Order Statistic Tree 사용

===== 마지막으로 남는 번호를 찾는 문제 =====
  * 위의 방법처럼 전체 수열을 다 구해서, 마지막 숫자만 출력해도 되긴 하지만, 좀더 효율적으로 풀수 있는 방법들이 있다.
  * k=2일때는 마지막 숫자를 closed form으로 구할 수 있다.
    * $ J_{n,2} = 1+2(n-2^{\lfloor{log_{2}n}\rfloor}) $
    * 비트 연산자를 활용하면 아래처럼 구현할 수 있다.
    * <dkpr py>
def josephus(n):
    return ~(1 << n.bit_length()) & ((n << 1) | 1)
</dkpr>    
  * 일반적으로는 아래 점화식을 이용해서 O(n)에 풀 수 있다
    * $ J_{n,k} = (J_{n-1,k}+k){\bmod  n},{\text{ with }}J_{1,k}=0 $
      * 이 식은 0-base 기준으로 계산한 값이라서, 계산이 끝나면 1을 더해줘야 한다
    * 코드는 이런식이 된다
    * <dkpr py>
def josephus(n, k):
    answer = 0
    for i in range(2, n + 1):
        answer = (answer + k) % i
    return answer + 1
</dkpr>    
  * k가 작을 때에는 O(klogn)에 계산할 수 있는 다른 점화식이 있다
    * $ {\displaystyle g(n,k)={\begin{cases}0&{\text{if }}n=1\\(g(n-1,k)+k){\bmod {n}}&{\text{if }}1<n<k\\\left\lfloor {\frac {k((g(n',k)-n{\bmod {k}}){\bmod {n}}')}{k-1}}\right\rfloor {\text{where }}n'=n-\left\lfloor {\frac {n}{k}}\right\rfloor &{\text{if }}k\leq n\\\end{cases}}} $
      * g(n,k)은 앞에서 쓰던 J_n,k와 같은 값이다. 0-base 이다.
    * 코드는 이런 식이 된다.
    * <dkpr py>
def josephus(n, k):
    def _josephus(n):
        if n == 1:
            return 0
        if k > n:
            return (_josephus(n - 1) + k) % n    
        res = _josephus(n - n // k) - n % k
        return res + (n if res < 0 else res // (k - 1))
    
    return (n if k == 1 else _josephus(n) + 1)
</dkpr>
 
==== 관련 문제 ====
  * [[ps:problems:boj:2164]] : k=2 인 경우.
  * [[ps:problems:boj:11025]]: k≤n≤5,000,000. O(n) 알고리즘 필요
  * [[ps:problems:boj:1179]] : n≤10*15, k≤90. O(klogn) 알고리즘 필요