파 티 션 게임(SG 함수)

Partitioning Game ：http://acm.hust.edu.cn/vjudge/contest/view.action?cid=112620#problem/D 전송 문:nefu
문제 면 설명:
Time Limit:4000MS     Memory Limit:32768KB     64bit IO Format:%lld & %llu
Submit  Status
Description
Alice and Bob are playing a strange game. The rules of the game are:
1.      Initially there are n piles.
2.      A pile is formed by some cells.
3.      Alice starts the game and they alternate turns.
4.      In each tern a player can pick any pile and divide it into two unequal piles.
5.      If a player cannot do so, he/she loses the game.
Now you are given the number of cells in each of the piles, you have to find the winner of the game if both of them play optimally.
Input
Input starts with an integer T (≤ 1000), denoting the number of test cases.
Each case starts with a line containing an integer n (1 ≤ n ≤ 100). The next line contains n integers, where the ith integer denotes the number of cells in the ith pile. You can assume that the number of cells in each pile is between 1 and 10000.
Output
For each case, print the case number and 'Alice' or 'Bob' depending on the winner of the game.
Sample Input
3
1
4
3
1 2 3
1
7
Sample Output
Case 1: Bob
Case 2: Alice
Case 3: Bob
제목 의 대의:
n 더미 아 이 템,각 더미 아 이 템 은 여러 개 로 구성 되 어 있 습 니 다.Alice 와 Bob 은 돌아 가면 서 순서대로 이 아 이 템 들 을 조작 합 니 다.매번 에 그 중의 한 무 더 기 를 서로 다른 개수 로 나 누 어야 합 니 다.마지막 으로 더 이상 조작 할 수 없 는 사람 이 경 기 를 지게 됩 니 다.
제목 분석:
모든 물품 의 분할 은 서로 독립 되 어 있 기 때문에 우 리 는 SG 함수 로 처리 할 수 있 습 니 다.먼저 한 무 더 기 를 계산 할 수 있 습 니 다.a 개의 물품 으로 구 성 된 더미 에 대해 분할 할 수 있 는 후계 방법 은(1,a-1),(2,a-2),(3,a-3),(a-1)/2,a-(a-2)/2 가 있 습 니 다.
같은 무더기 로 분 단 된 두 무더기 도 서로 독립 되 어 있 기 때문에 SG 정리 로 SG(x)=mex{SG(1)^SG(a-1),SG(2)^SG(a-2), SG(3)^SG(a-3), ... ,SG((a-1)/2)^SG(a-(a-1)/2)};
마지막 답 은 SG(a1)^SG(a2)^SG(a3)^...^SG(an);
코드 구현:

#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

int hashsz[10010],sg[10010];
void getsg()
{
    memset(sg,0,sizeof(sg));
    for(int i=1;i<=10000;i++) ///sg[0]=0;
    {
        memset(hashsz,0,sizeof(hashsz));
        for(int j=1;j+j<i;j++)
        {
            hashsz[sg[j]^sg[i-j]]++;
        }
        for(int j=0;j<=10000;j++)
        if(!hashsz[j])
        {
            sg[i]=j;
            break;
        }
    }
}

int main()
{
    getsg();
    int t,n,a,casenum=0;
    int ans;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        ans=0;
        for(int i=0;i<n;i++)
        {
            scanf("%d",&a);
            ans=ans^sg[a];
        }
        if(ans)
        printf("Case %d: Alice
",++casenum);
        else
        printf("Case %d: Bob
",++casenum);
    }
    return 0;
}