n个人（编号从0开始），从1开始依次报数，报到k的那个人退出，并继续循环报数，问最后剩下的人的编号这个问题还是要从递归的角度去考虑设$f_{n-1}$表示n个人时最后剩下的那个人那么对于n个人的情况，第一个出局的人是k-1，之后就相当于是从k开始的n-1个人的约瑟夫环问题所以很容易得到递推式$f_n = (f_{n-1} + k)%n$同样的如果要求第m个出局的人，也可以用上述公式$f_{n,m}=(f_{n-1,m-1}+k)%n$对于$k \ll n$的情况，考虑$f_{i+x-1}=(f_{i-1}+x*k)%(i+x-1)$，当$f_{i-1}+x*k\leq i+x-1$时不会取模，所以快速递推
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
| ll J(ll n, ll k)
{
if(k==1) return n;
ll ans = 0, i = 2;
while(i<=n)
{
ll cnt = (i-ans-2)/(k-1);
if(!cnt)
{
ans = (ans + k)%i;
i++;
}
else
{
if(i+cnt>n)
{
ans = (ans + k*(n-i+1))%n;
break;
}
else
{
i += cnt;
ans = (ans + k*cnt)%i;
}
}
}
return ans + 1;
}
|
另外对于k=2的特殊情况，可以考虑当n为2的幂次的时候答案就是1，所以当n为$2^x+y$的形式时，答案为$2*y+1$
求第x个人是第几个死的（0下标）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
| ll solve(ll n, ll k, ll x)
{
ll ans = 0;
while(n)
{
x = (x+n)%n;
if(k>n) x += (k-x-1+n-1)/n*n;
if((x+1)%k==0)
{
ans += (x+1)/k;
break;
}
else
{
if(k>n)
{
ans += x/k;
ll tmp = x;
x = x-(x/n+1)*(x/k)+(x+n)/n*n-k;
n -= tmp/k;
}
else
{
ans += n/k;
x = x-x/k;
x += n-n/k*k;
n -= n/k;
}
}
}
return ans;
}
|