板子理解题 //以下两个定理都不是很会证哎, 只是大概知道思想.
第一种 , O(n)的递推. f[n] 代表是有n个人时最后当选的那个人的编号. Code （// n个人的编号是从0开始的.）
/** @Cain */ const int maxn=1e6+5; int f[maxn]; //f[i] 表示有i个人时2最后获胜的是哪个编号的. //直接保存的每一种人数的情况. int Josephus1(int n,int k) { f[1] = 0; for(int i=2;i<=n;i++) f[i] = ( f[i-1] + k ) % i; return f[n]; } //直接输出答案 int Josephus2(int n,int k) { int res = 0; for(int i=2;i<=n;i++) res = ( res + k ) % i; return res; }当然如果n很大, 这样肯定就是不行的, 所以还有另一种优化的方法, 对于k比较小的, n很大的比较适合,
Code
int Josephus(int n,int k) { int res ; if(n == 1) return 0; if(n < k){ res = 0; for(int i=2;i<=n;i++) res = (res + k) % i; return res; } res = Josephus(n-n/k,k); if(res < n % k) res = res - n % k + n; else res = res - n%k + (res - n % k) / (k - 1); return res; }