貼一篇博客，寫的還行
經(jīng)典約瑟夫問題的快速求解
除了循環(huán)鏈表模擬，和動(dòng)態(tài)規(guī)劃求解
還可以利用樹狀數(shù)組，樹狀數(shù)組的時(shí)間復(fù)雜度為O（n * (logn)^2）
算是非?？斓牧?br>
而且不同于動(dòng)態(tài)規(guī)劃只能在報(bào)數(shù)長度一定的情況下解決約瑟夫問題。
樹狀數(shù)組可以在報(bào)數(shù)長度不定的情況下解決，相當(dāng)于對模擬做了一個(gè)優(yōu)化。a
emmmmmmmm......
首先，我們可以有這樣遞推的思路：不斷加k模n，并減去其數(shù)字前走了的人即為當(dāng)前人的真實(shí)編號(hào)（即是這一輪應(yīng)踢走的人的編號(hào)），如何快速維護(hù)每個(gè)人其前走了的人的和，答案為樹狀數(shù)組。
現(xiàn)在模擬一下過程，假設(shè)有6個(gè)人，k=3（每報(bào)3個(gè)，走一個(gè)人）。
初始狀態(tài)：1 2 3 4 5 6
用樹狀數(shù)組在每個(gè)人的位置加一，可得前綴和：1 2 3 4 5 6
現(xiàn)在1+2(其實(shí)是k-1)=3走了:1 2 4 5 6
用樹狀數(shù)組在3的位置減1，可得前綴和：1 2 2 3 4 5
再走了3+2=5，5%（6-1）=5（走了一個(gè)人，故6需減1）等等，此時(shí)并不是走了5，而是在樹狀數(shù)組中前綴和為5的數(shù)字，由上可知走了6：1 2 4 5
用樹狀數(shù)組在6的位置減1，可得前綴和：1 2 2 3 4 4
又按5+2=7，7%（6-2）=3，但這時(shí)在樹狀數(shù)組的前綴和中查找3，可見是第四個(gè)人的狀態(tài)為3，故此回合走了4：1 2 5
用樹狀數(shù)組在4的位置減1，可得前綴和：1 2 2 2 3 3
又按3+2=5，5%（6-3）=2，在樹狀數(shù)組中查找二，可見即為2，
故此回合走了2：1 5，
前綴和改為：1 1 1 1 2 2
最后2+2=4，4%（6-4）=2，在樹狀數(shù)組中查找2，可見為5，
故最后只剩1了。
因?yàn)榍熬Y和是單調(diào)的，所以查找可以用二分。
可得序列為：3 6 4 2 5 1
這個(gè)東西還挺有意思的，要是遇到需要求約瑟夫問題，但是報(bào)數(shù)長度不定可以用bit模擬，比循環(huán)鏈表不知道穩(wěn)到哪去了
模板可以看一個(gè)例題
POJ - 2886
=.=貼題目
N children are sitting in a circle to play a game.
The children are numbered from 1 to N in clockwise order. Each of them has a card with a non-zero integer on it in his/her hand. The game starts from the K-th child, who tells all the others the integer on his card and jumps out of the circle. The integer on his card tells the next child to jump out. Let A denote the integer. If A is positive, the next child will be the A-th child to the left. If A is negative, the next child will be the (?A)-th child to the right.
The game lasts until all children have jumped out of the circle. During the game, the p-th child jumping out will get F(p) candies where F(p) is the number of positive integers that perfectly divide p. Who gets the most candies?
Input
There are several test cases in the input. Each test case starts with two integers N (0 < N ≤ 500,000) and K (1 ≤ K ≤ N) on the first line. The next N lines contains the names of the children (consisting of at most 10 letters) and the integers (non-zero with magnitudes within 108) on their cards in increasing order of the children’s numbers, a name and an integer separated by a single space in a line with no leading or trailing spaces.
Output
Output one line for each test case containing the name of the luckiest child and the number of candies he/she gets. If ties occur, always choose the child who jumps out of the circle first.
Sample Input
4 2
Tom 2
Jack 4
Mary -1
Sam 1
Sample Output
Sam 3
=.=貼代碼
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<iostream>
#include<math.h>
#include<stdlib.h>
using namespace std;
const int maxn = 500050;
int bit[maxn]; //樹狀數(shù)組
char name[maxn][15];
int val[maxn];
int a[39]= {1,2,4,6,12,24,36,48,60,120,180,240,360,720,840,1260,1680,
2520,5040,7560,10080,15120,20160,25200,27720,45360,50400,
55440,83160,110880,166320,221760,277200,332640,498960,500001};
int b[39]= {1,2,3,4,6,8,9,10,12,16,18,20,24,30,32,36,40,48,60,64,72,
80,84,90,96,100,108,120,128,144,160,168,180,192,200,1314521};
int n;
int sum(int i)
{
int s = 0;
while(i > 0)
{
s+=bit[i];
i-=(i&-i);
}
return s;
}
void add(int i,int x)
{
++i;
while(i<=n)
{
bit[i] += x;
i += (i&-i);
}
}
int binary(int id)
{
int l = 0,r = n;
while(r-l>1)
{
int mid = (l+r) >> 1;
if(sum(mid) <= id) l = mid;
else r = mid;
}
return l;
}
int main()
{
int k;
while(~scanf("%d%d",&n,&k))
{
--k;
memset(name,0,sizeof(name));
memset(val,0,sizeof(val));
memset(bit,0,sizeof(bit));
for(int i=0;i<n;i++)
{
scanf("%s %d",name[i],&val[i]);
add(i,1);
}
int candy = -1;
int iu = 0,Max = 0,p = 0;
while(a[iu] <= n)
iu++;
p = a[iu-1];
Max = b[iu-1];
for(int i=1;i<p;i++)
{
add(k,-1);
int mod = n-i;
int id = sum(k) + val[k] + (val[k]>0?-1:0);
id = (id%mod + mod)%mod;
k = binary(id);
}
printf("%s %d\n",name[k],Max);
}
}
