UVA 1558 - Number Game

제목 링크
제목: 20 안의 숫자는 매번 한 개의 숫자를 선택할 수 있다. 그리고 그 배수, 그리고 이미 선택한 배수의 배수 조합의 숫자는 다시 선택할 수 없다. 먼저 선택할 수 없는 사람이 진다. 이기는 방법을 묻는다.
사고방식: dp기억화를 이용하여 해답을 구하고 방안을 출력하려면 첫 번째 단계를 열거하면 된다. 상태 이동 과정에서 숫자를 선택하고 대응하는 변화를 함수로 쓴다. 그 다음은 일반적인 바둑 문제이다. 필승태 이후에는 필패태가 있고 필패태 이후에는 모두 필승태이다.
코드:

#include <stdio.h>
#include <string.h>

const int N = 1050005;
int t, n, w, start, dp[N], ans[25], an;

int getnext(int state, int x) {
	for (int i = x; i <= 20; i += x) 
 		if (state&(1<<(i - 2)))
   			state ^= (1<<(i - 2));
	for (int i = 2; i <= 20; i++) {
		if (state&(1<<(i - 2))) {
			for (int j = x; i - j >= 2; j += x) {
				if (!(state&(1<<(i - j - 2)))) {
					state ^= (1<<(i - 2)); 
					break;
				}
   			}
  		}
 	}
 	return state;
}

int dfs(int state) {
	if (dp[state] != -1) return dp[state];
	if (state == 0) return dp[state] = 0;
	
	for (int i = 2; i <= 20; i++) {
		if (state&(1<<(i - 2))) {
			if (dfs(getnext(state, i)) == 0)
				return dp[state] = 1;
  		}
 	}
 	return dp[state] = 0;
}

int main() {
	int cas = 0;
	scanf("%d", &t);
	memset(dp, -1, sizeof(dp));
	while (t--) {
		start = 0; an = 0;
		scanf("%d", &n);
		for (int i = 0; i < n; i++) {
			scanf("%d", &w);
			start |= (1<<(w - 2));
  		}
  		for (int i = 2; i <= 20; i++) {
  			if (start&(1<<(i - 2))) {
  				if (dfs(getnext(start, i)) == 0)
  					ans[an++] = i;
     		}
    	}
    	printf("Scenario #%d:
", ++cas);
    	if (an) {
    		printf("The winning moves are:");
    		for (int i = 0; i < an; i++)
    			printf(" %d", ans[i]);
  			printf(".
");
     	}
     	else printf("There is no winning move.
");
     	printf("
");
 	}
	return 0;
}