ヨセフスの問題

wataさんライブラリの解読．

ヨセフス数

J(n,m,k):n人の輪からm人毎に殺していった時にk番目に殺される人の番号[0, n-1]

まずn人を以下のように並べる．
0,1,2,…,m-2,m-1,m,…,n-3,n-2,n-1
とりあえず1人殺してみるとm-1が消える．
0,1,2,…,m-2,,m,…,n-3,n-2,n-1
この状態を初期状態と考え，J(n-1,m,k-1)を用いてJ(n,m,k)を表したい．J(n-1,m,k-1)は，下のような初期状態で0からm人を数え始めた時の答えに等しい．
n-m,n-m+1,n-m+2,…,n-2,,0,…,n-m-3,n-m-2,n-m-1
即ち，J(n,m,k)とJ(n-1,m,k-1)とは値がm異なり，
J(n,m,k)=(J(n-1,m,k-1)+m)%n
が成立する．
（%nは値が[0, n-1]に収まるようにするため）
また，k=0の時は便宜上-1とする．

漸化式

J(n,m,0)=-1
J(n,m,k)=(J(n-1,m,k-1)+m)%n

計算量

O(k)

逆ヨセフス数

J^-1(n,m,x):n人の輪からm人毎に殺していった時にx番が殺されるターン数[1, n]

各ターンにおけるx番の位置を更新していくことで殺されるターン数を求める．
先ほどと同じように，n人を以下のように並べる．
0,1,2,…,m-2,m-1,m,…x-1,x,x+1,…,n-3,n-2,n-1
とりあえず1人殺してみるとm-1が消える．
0,1,2,…,m-2,,m,…,x-1,x,x+1,…,n-3,n-2,n-1
この時，次のm人を数え始めるのは，m番の人からである．つまり，数え始めの人の番号を0とすると，以下のようになる．
n-m,n-m+1,n-m+2,…,m-2,,0,…,x-m-1,x-m,x-m+1,…,n-m-3,n-m-2,n-m-1
即ち，n人の時にx番だった人は，n-1人の時にはx-m番（の位置にいる）と考えることが出来る．従って，ターン毎にx番の人の位置を更新していき（ただし，現在の人数で剰余を取ること），位置が(n-ターン数)（=-1，[]の位置に相当）になったらその人が殺されたとしてターン数を返す．

計算量

O(n)