0 开始报, 如此反复, 最后一个剩下的为胜利者.今天的问题并不是经典的约瑟夫环问题，而有一定的进阶. 在本题中,m1 will be killed, and the next one counting from zero. And so on and so on and so on and so on.Today, I want to give you a similar problem but not the classic Joseph's ring problem, with a certain degree of progression: in this case,
约瑟夫环, 简而言之就是 n n 个人 A={a_0,a_1, ldots, a_{n-1} } A={a ,a 1 ,…,a n−1 } 围成一圈, 第一个人从 0 开始报数, 报到 m-1 m−1 的人将被杀, 下一个人接着从 0 开始报, 如此反复, 最后一个剩下的为胜利者. 如 n=5 n=5, m=2 m=2 时, 被杀顺序为 a_1,a_3,a_0,a_4 a 1 ,a 3 ,a ,a 4 . 此时 a_2 a 2 为胜利者. 今天的问题并不是经典的约瑟夫环问题，而有一定的进阶. 在本题中, m m 是循环变化的, 存在一个序列 M={m_0, m_1, ldots, m_{k-1}} M={m ,m 1 ,…,m k−1 }, 第一次报到 m_0 - 1 m −1 出列, 第二次报到 m_1 -1 m 1 −1 出列， ldots …, 报到 m_{k-1} -1 m k−1 −1 后, 重新从 m_0 m 开始, 求最后的胜利者(下标从 0 开始). Joseph's ring, in short, is a circle of n n people A={a_0,a_1, ldots, a_{n-1} } A={a ,a 1 ,…,a n−1 }, the first one counting from zero, to the m-1 m−1 will be killed, and the next one counting from zero. And so on and so on and so on and so on. For example, when n=5 n=5, m=2 m=2, the order will be a_1,a_3,a_0,a_4 a 1 ,a 3 ,a ,a 4 , and a_2 a 2 is a winner. Today, I want to give you a similar problem but not the classic Joseph's ring problem, with a certain degree of progression: in this case, m m is cyclic, and m m belongs to the sequence M={m_0, m_1, ldots, m_{k-1}} M={m ,m 1 ,…,m k−1 }, the first person will be killed if he count m_0 -1 m −1, and next will be killed if count m_1 -1 m 1 −1, ldots …, and when reached m_k m k , it moves down again to m_0 m . Find the number of the last person who will win the game(index start from 0).
标签： HBC231193XORTREE 数据结构 线段树 树链剖分约瑟夫环Pro题解
