【ジョセフリング変形】UVa 1394-And Then There Was One

まずこの問題を見てすぐにチェーン時計から飛び出した.その後も続けてみると、チェーン時計法の時間的複雑さはO(n*k)で、TLEになるに違いない.
家の分析のように见てあまり理解していないで、それからこの自分が理解するのがもっと容易であることを発见します
问题补充:n个人(番号0~(n-1)),0から报数,报到(m-1)の脱退,残りの人は引き続き0から报数を始める.胜者の番号を求める.番号0~(n-1)は意味があり、nを模するので、0-(n-1)で操作すると、一人目(番号は必ず(m-1)mod n)がわかる列を出た後、残りのn-1人は新しいジョセフリングを構成した(k=m mod nの番号の人から):
k k+1 k+2...n-2,n-1,0,1,2,...k-2そしてkから0を報告します.今、彼らの番号を変換します.k-->0 k+1-->1 k+2-->2......k-2-->n-2変換後、完全に(n-1)になりました.个人报数のサブ问题、もし私达がこのサブ问题の解を知っているならば:例えばxは最后の胜者で、それでは上のこの表によってこのxを戻すのはちょうどn个人の情况の解ではありませんか?!!戻る公式はとても简単で、みんながすべて押し出すことができることを信じます:x'=(x+k)mod n;
だから私たちはずっとこの過程を繰り返すだけで最初の人の番号を求めることができます.この人の最終的な番号は0(彼一人しか残っていない):0->(0+k)%2->((0+k)%2+k)%3->......f[n]=(f[n-1]+k)%n,f[1]=0です.  f[i]i人がいることを示す場合、最後の勝者番号
==========================================
この考え方は古典的なジョセフリング問題に適用されることに注意してください.
==========================================
次は変形します...
今この問題はmから始まり、つまりまず(m-1)番号の人が出て行く..そして普通のジョセフリングと同じになる.だからf[n]=(f[n-1]+m)%n単独で計算すればいい.他のf[i]=(f[i-1]+k)%i;(1 
コードは次のとおりです.

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstdlib>
 4 #include<cstring>
 5 using namespace std;
 6 const int maxn = 10005;
 7 int f[maxn];
 8 int main()
 9 {
10     int n, k, m, step, cnt;
11     while(~scanf("%d%d%d", &n, &k, &m))
12     {
13         if(!n && !k && !m)   break;
14         f[1] = 0;
15         for(int i = 2; i < n; i++)
16         {
17             f[i] = (f[i-1]+k)%i;
18         }
19         int ans = (f[n-1]+m)%n;
20         printf("%d
", ans+1);
21     }
22     return 0;
23 }