# CFR 768 E. Game of Stones ( SG Value, DP )

Problem - 768E - Codeforces

N 堆石頭，輪流取，不能取的輸。對於某一堆石頭，不能拿走同個數量的石頭兩次。求後手勝敗。

First line consists of a single integer n (1 ≤ n ≤ 1e6) — the number of piles.
Each of next n lines contains an integer si (1 ≤ si ≤ 60) — the number of stones in i-th pile.

Codeforces #399 E. Game of Stones - kmjp's blog

O( N ) / O( S )

```#include <bits/stdc++.h>
using namespace std;

const int MAXN = ( int ) 1e6;
const int MAXS = 60;

/*
map< pair< int, set< int > >, int > sg;

void dfs( int u, set< int > &op ){
if( sg.count( make_pair( u, op ) ) ) return;
if( u == 0 ){
sg[ make_pair( u, op ) ] = 0;
return;
}
set< int > bag;
for( int i = u; i; --i ){
if( op.count( i ) ) continue;
op.emplace( i );
dfs( u - i, op );
bag.emplace( sg[ make_pair( u - i, op ) ] );
op.erase( i );
}
for( int i = 0; ; ++i ){
if( not bag.count( i ) ){
sg[ make_pair( u, op ) ] = i;
return;
}
}
}
code above shows that sg[] = { 0, 1, 1, 2, 2, 2, 3, .., } */

int sg[ MAXS + 1 ];

int N;

signed main(){
for( int i = 0, val = 0, c = 0; i <= 60; ++i ){
sg[ i ] = val;
if( ++c == val + 1 ){
c = 0;
++val;
}
}
ios::sync_with_stdio( 0 );
int game = 0;
cin >> N;
for( int i = 0; i < N; ++i ){
int S; cin >> S;
game ^= sg[ S ];
}
if( not game ){
cout << "YES" << endl;
} else{
cout << "NO" << endl;
}
return 0;
}
```