[스프라그 그런디 정리] - BOJ_16895 : 님 게임 3

2023.05.09 - [PS] - [스프라그 그런디 정리] - BOJ_11868 : 님 게임 2

어제 푼 님 게임2에이어서 님 게임3.

님 게임 2에서는 단순히 xor로 그런디 수를 파악하여 게임의 승패만을 예측하는 것이었다면, 이 문제에서는

승리할 수 있는 경우의 수를 세는 것이 목적이다.

간단한 아이디어로 생각을 해보자.

xor를 하였을때, 1이 남는 비트들이 존재할 것이다.

첫번째 예시로 생각을 해보면,

$15=1111_2$

$11=1011_2$

$8 = 1000_2$

이고, 이를 xor하면

$1100_2$ 가 된다.

이때, 1인 비트중 최상위 비트는 $2^3$ 비트에 위치한 1이다.

이 때, 님게임 2에서 증명했듯이 현재 xor을 한 후 1인 최상위 비트를 가진 그런디 수들은,

값이 변경되었을 때 해당비트를 0으로 만들고 (값이 줄어드므로) 하위 비트들도 원하는 만큼 변경 시킬 수

있기 때문에   $10000_2$인 그런디 수를 몇을 줄여도, 하위 비트의 원하는 위치에 1을 위치 시킬 수 있다.

$01111_2이든, 01100_2이든, 00001_2이든$ 말이다.

따라서, 우리는 xor을 하였을때의 1인 비트 중 최상위 비트를 ‘보유’ 하고 있는

그런디 수의 개수= 내가 승리할 수 있는 가짓수가 된다고 볼 수 있다.

 

#include <bits/stdc++.h>

using namespace std;


int n,cnt;
int arr[1010];
int result;
int main(){
    cin>>n;
    for(int i=0; i<n; i++){
        cin>> arr[i];
        result=result^arr[i];
    }
    int i=0,highestBit=-1;
    while(result){
        if(result & 1) highestBit=i;
        result=result>>1;
        i++;
    }

    int isBitExist=1;
    for(int i=0; i<highestBit; i++){
        isBitExist= isBitExist << 1;
    }
    

    if(highestBit==-1) cout<<"0";
    else{
        for(int i=0; i<n; i++){
            if(arr[i]&isBitExist) cnt++;
        }
        cout<<cnt;
    }
    return 0;
    
}