【51nod1073】约瑟夫环1

题目大意：给定 \(N\) 个人围成一个圈，每隔 \(M\) 个人杀一个，求最后活着的人的编号。

题解：环会涉及模运算，所以先将 \(1 \rightarrow N\) 映射为 \(0 \rightarrow N-1\)，且报数从 \(0\) 开始，即：报数到 \(m-1\) 的人会被杀掉。假设已知 \(N-1\) 人时剩下的人的编号为 \(x\)，如何求得 \(N\) 个人时活着的人的编号是问题的关键。现在逆向考虑问题，即：游戏第一次杀人后的子问题和原问题之间的关系。假设第一次报数时，编号为 \(k-1\) 的人被杀，则第 \(k\) 个人到第 \(k-2\) 个人组成的新环恰好构成了一个 \(N-1\) 个人的子问题，且 \(k \rightarrow 0,k-2 \rightarrow n-2\)。可知，\(f[i]=(f[i-1]+k)\% i\)，其中 \(k=m\% n\) 。因此，最后的递推公式为：\(f[i]=(f[i-1]+m)\% i,f[1]=0\)。

代码如下

#include <bits/stdc++.h>

using namespace std;

const int maxn=1e6+10;

int n,m,f[maxn];

void solve(){

    f[1]=0;

    for(int i=2;i<=n;i++)f[i]=(f[i-1]+m)%i;

    printf("%d\n",f[n]+1);

}

int main(){

    scanf("%d%d",&n,&m);

    solve();

    return 0;

}