可能是你能找到的最全的关于约瑟夫环的一切

Reference

https://blog.csdn.net/u011500062/article/details/72855826
https://www.cnblogs.com/Vikyanite/p/12236482.html
https://www.cnblogs.com/Vikyanite/p/12236482.html

万恶之源

n 个人围成一圈，从第一个人开始报数,数到 m 的人出列，再由下一个人重新从 1 开始报数，数到 m 的人再出圈，依次类推，直到所有的人都出圈，请输出依次出圈人的编号。

朴素做法

开个链表，略（逃
时间复杂度：$\Theta(n^2)$

线性做法

要想了解这个做法，最好的是对我们删除的做法做些改变
按照朴素的做法，我们从上一个人的下一个人开始数，遇到被删除的人就跳过，直到数到 m。这种做法最大的坏处就是上一个人和下一个人之前的人的状态不能很快得知，需要遍历过去。
那大家有什么想法吗？有想法也是我来说

让我们试试把每一次数过的数都放到后面去，如图(假设 n=8, k=3)

然后删除的时候就只用划掉最后一个数了
那这样有什么好处吗？
让我们来观察这个6（6：为什么是我）
我们先从第三行看起，我们可以观察到，从上面到下面这个过程，6往后移了3格。再看看第4行，虽然6从第4位跑到了第1位，但实际上还是移动了3格。
于是我们可以简单地得出递推公式：$f(n)=(f(n-1)+k)\bmod i(1\le i\le n)$，注意下标在 0~n-1 之间，最后答案还要 +1

二分算法

线性算法已经到极限了吗？并不是，我们注意到，当 $n>=2*k$ 时，线性算法一次只能删一个人，但是其实我们可以把一圈内的删除合并起来
那具体怎么做呢？很简单
看图

我们想让它从第一行跳到第三行，这时我们观察到，因为我们把前两组都移到后面去了，所以第三行最前面n%k个数就是第一行的最后面n%k个数。于是我们用递归，当获取第三行时，先减去n%k，如果为负，说明符合，加上n就是原来的位置。我们再来观察前面两组数，比如说3，它是第二组的数，于是我们让它除以 (k-1)，就是它在的组号-1，也就是它前面被删除的数，于是加上就是它原来的位置了
上代码

ll jose(int n,int k){
    if(n<k){
        ll res=0;
        for(int i=2;i<=n;i++){
            res=(res+k)%i;
        }
        return res;
    }
    ll res=jose(n-n/k,k);
    res-=n%k;
    return res<0?res+n:res/(k-1);
}

这个算法的时间复杂度是 $\Theta(klogn)$

树状数组处理输出被删除的人

这个算法的时间复杂度是 $\Theta(n*log^2n)$
剩下的先咕着终于填完坑了

#include<iostream>
#define N 1000
using namespace std;

inline int lowbit(int x){
    return x&-x;
}
int c[N],n,m;
void update(int x,int k){
    while(x<=n){
        c[x]+=k;
        x+=lowbit(x);
    }
}

int query(int x){
    int ans=0;
    while(x>=1){
        ans+=c[x];
        x-=lowbit(x);
    }
    return ans;
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        update(i,1);
    }
    int no=1;
    for(int i=1;i<=n;i++){
        int l=1,r=n;
        int c_r=(no+m-2)%(n-i+1)+1;
        while(l<=r){
            int mid=((r-l)>>1)+l;
            int c_l=query(mid);
            
            if(c_l<c_r){
                l=mid+1;
            }else{
                r=mid-1;
            }   
        }
        no=c_r;
        update(l,-1);
        cout<<l<<" ";
    }
}

这也很好理解
关于思路：其实朴素的链表做法最大的坏处在于寻找下一个数的过程，需要一个一个遍历过去看看有几个人，但是如果我们已经知道前面有几个人呢？
更进一步，知道前面有几个人，是不是和前缀和很像呢？于是我们就可以想到用树状数组
但是有点麻烦的是前面有几个人往往需要做边界处理，于是我们改为存包括自己在内的前面的人的个数
每次我们计算出前面人的个数，然后用二分找到对应前缀和，然后使用树状数组修改
然后呢，我们通过 $no+m-2\pmod{n-i+1}+1$ 来计算前面的人的个数（n从1开始，初始 no=1）
不妨来试试这个式子 当 n=5,m=3 时式子输出的值是 3,1,…

哇，刚好符合诶

于是题目就做好啦

各种奇奇怪怪的变式

继续鸽着