【BestCoder Round #75 1004】King's Game

  考时自然是交了个表上去。

  不过也是很显然的一个递推，记f[n][i]表示剩n个人，按照隔i,i+1,i+2,i+3,...i+n-2个人出队的顺序最终幸存者的编号。(为了方便先把人按0...n-1编号)

  那么递推式就是\(f[n][i]=(f[n-1][i+1]+i)\ mod\ i\)，边界条件\(f[1][i]=0\)。n个人时幸存者即为\(f[n][1]+1\)。

#include <cstdio>
#include <cstring>
using namespace std;
const int maxn=5010;

int f[2][maxn];
int ans[maxn];
int n,T;

int main()
{
	for (int i=1;i<=5000;i++)
	{
		int o=i&1,po=o^1;
		for (int j=1;j+i<=5005;j++) f[o][j]=(f[po][j+1]+j)%i;
		ans[i]=f[o][1]+1;
	}
	scanf("%d",&T);
	while (T--)
	{
		scanf("%d",&n);
		printf("%d\n",ans[n]);
	}
	return 0;
}