未来遗迹

题目链接：http://codeforces.com/contest/1194/problem/D

题目大意是在标为0到n的n+1个格子中的最右边（指标为n的那一个），上有一个物品，游戏双方每次可以选择该物品左移（指标减小的方向）1格，2格或者\(k\ (k \ge 3)\)格。Alice先手，当有人试图把物品移出0号位置时该人判输。问该游戏谁会胜利。

物品放在0位置时是一个先手必败状态。如果一个位置能走到的位置中有一个是先手必败位置，该位置是先手必胜位置。如果一个位置能走到的位置全部都是先手必胜位置，该位置是一个先手必败位置。

首先，如果假设没有k的存在，每次只能移动1或2格，由于1和2构成了全部的3的非零余数，后手的人总可以使得当前移动的总步数是3的倍数。即如果\( n=0,3,6,\cdots,3k,\cdots \)总是先手必败。当n除3得别的余数时，先手可以通过一步使得剩下的距离为3的倍数，此时先手胜。

同样的道理，如果\( k=3 \)，由于构成了4的全部非零余数，因此当$ n%4=0 $时先手必败，否则先手必胜。

当k较大时，此时设 \( k \ge 5 \) ，如果k模3得到了1或者2，实际上和之前的情况没有变化。当k模3等于0时，原本处在 \( k \) 位置的可以通过一步走到0，因此 \( k \)位置变为一个先手必胜位置， \( k+1 \)位置能走到的地方都是先手必胜位置，所以\( k+1 \)位置是一个先手必败位置。此后把\( k+1 \)位置当作0号位置考虑，就能发现先手必败位置的指标是按照$ k+1 $进行分块，块内部的相对于第一个格子的第\( k+1-4,k+1-8,\cdots,k+1-i*k,\cdots,3,0 \)的位置是必败位置。

AC代码

#include <iostream>
#include <stdio.h>
#include <cstring>
#include <vector>
#include <algorithm>
#include <queue>
#include <stack>

#ifndef ONLINE_JUDGE
#define debug(x) cout<<#x<<"=="<<x<<endl
#else
#define debug(x) ;
#endif // !

#ifdef _MSC_VER
#define scanf scanf_s
#endif // _MSC_VER


using namespace std;
const int MAXN = 1e9 + 7;
const int INF = (int)1e9 + 7;



int main() {
	int T;
	scanf("%d", &T);
	while (T--) {
		int n, k;
		scanf("%d%d", &n, &k);
		bool bobwin;
		if (k == 3) {
			bobwin = n % 4 == 0;
		}
		else if (k % 3 != 0) {
			bobwin = n % 3 == 0;
		}
		else {
			n %= (k + 1);
			bobwin = n > k + 1 - 4 ? false : n % 3 == 0;
		}
		printf("%s\n", bobwin ? "Bob" : "Alice");
	}
	return 0;
}