约瑟夫环变形问题LA 3882

约瑟夫环不再赘述

对于约瑟夫环变形问题 当问题规模变大，我们只考虑最后被删除的那个人
假设从0开始报数
他在最后一次，只剩自己的时候，报数为0 记 dp[1]=0;
倒数第二次，还剩下两个人 ，所以 这个人这一轮的序号应该是 (dp[1]+k)%2
倒数第三轮 此人序号应为 dp[3] = (dp[2] +k)%3

因此可以得出递推关系 dp[i] = (dp[i-1]+k)%i

dp[n] 即为最后一个人的第一轮序号

这是满足第一个人 从0开始计算，删去第k个人的情况 第一个被删去的人的序号应该为 k-1

现在题目要求第一个被删去的序号为 m ，所以开始计算的序号应该为 m-k+1

因此 dp[n] 也应该 往前推 dp[n]=(dp[n] + m-k+1)%n

要注意，恰好为n的时候 dp[n] = n 而不是为 0
负数的情况要注意

#include <bits/stdc++.h>
using namespace std;
const int maxn=10005;
int n,m,k;
int dp[maxn];
int main()
{
    while(scanf("%d%d%d",&n,&k,&m)&&(n||m||k))
    {
        memset(dp,0,sizeof(dp));
        dp[1]=0;
        for(int i=2;i<=n;i++) dp[i] = (dp[i-1]+k)%i;
        int ans = (dp[n]+m-k+1)%n;
        ans = ((ans)%n+n)%n;
        if(ans==0) ans=n;
        printf("%d\n",ans);
    }
    return 0;
}