题目
点这里看题目。
分析
首先注意到黑白石子是独立的两个游戏，我们可以分别求出它们的 \(sg\) 值，然后异或起来得到整个游戏的 \(sg\) 值。
之后分开考虑，白石子就是 Nim，因此白石子的 \(sg\) 值就是每堆白石子的数量的异或。
接着考虑黑石子。注意到我们每次只能操作最少的一堆，那么将所有石子堆按照数量排序后，我们就相当于每次只能操作第一堆，如果操作完了就换下一堆。在有序的情况下，我们可以从后往前合并每一堆。因此如果有 \(k\) 堆黑石子，我们可以设排序后，第 \(i\) 堆有 \(b_i\) 颗石子，而 \([i,k]\) 的石子堆组成的局面的 \(sg\) 值为 \(f_i\)。
考虑从 \(f_{i+1}\) 转移到 \(f_i\)。类似于 Nim 的推导过程，我们可以设计出 \(g_j\) 为第 \(i\) 堆石子还剩 \(j\) 颗时局面的 \(sg\) 值。那么就有：
手玩一下可以找出规律：
尝试使用这个规律计算任意一个位置的 \(f\)。如果 \(i<k,b_i<b_{i+1}\)，那么 \(f_i\) 一定为 \(b_i-1\)；否则就是 \(b_i=b_{i+1}\)，此时 \([b_i\le f_{i+1}]\) 取决于 \(i\) 在连续相同段中所处的位置和这一段相同的值在 \(b\) 中所处的位置，总结如下：
- 如果 \(b_i=\max_{1\le j\le k} b_j\)，那么 \(f_i=b_i-(k-i)\bmod 2\)；
- 否则，设在 \([i,k]\) 中有 \(s\) 堆石子数量与 \(b_i\) 相同，那么 \(f_i=b_i-[(s-i)\bmod 2=0]\)；
在原问题中我们只关心 \(f_1\)，而 \(f_1\) 仅仅取决于 \(b_1\) 和 \(b_1\) 所处的位置，所以我们可以从大到小枚举 \(b_1\)。枚举好 \(b_1\) 之后，假设在 \(a\) 中有 \(t\) 堆石子数量为 \(b_1\)，此时我们有 \(2^t\) 种方式选出 \(s\) 为奇数的情况，有 \(2^t-1\) 选出 \(s\) 为偶数的情况。下面是讨论：
-
如果我们令 \(b_1=\max_{1\le j\le k}b_j\)，那么这就意味着除了选出来的一些数量都为 \(b_1\) 的黑石子堆，其余都是白石子。我们可以分 \(s\) 为奇数和偶数，这样白石子的异或和是确定的，我们只需要检查此时黑白 \(sg\) 值的异或和是否为零，并计算贡献即可；
-
否则，这说明一定有数量超过 \(b_1\) 的石子堆被涂黑。此时黑石子的 \(sg\) 值和所有 \(\le b_1\) 的白石子的 \(sg\) 值可以被算出，不妨设已知的 \(sg\) 值为 \(v\)，我们相当于要从后面的石子堆中选出一个真子集（这个子集内的石子堆会被染白），使得子集中的石子异或出的值和 \(v\) 异或后得到 0。
这其实就是计算方程解的数量的问题，在 \(\bmod 2\) 意义下计算解数是很容易的：我们只需要判断 \(v\) 能否被解得，那么解的数量就是 \(2^{\text{*元个数}}\)。而一个数是否为*元取决于它是否在基内，因此我们可以维护一个异或线性基，以此判断 \(v\) 能否被解出，同时非*元的数量就是基的大小。
当然，我们还需要检查如果后面的石子堆全选了是否会得到 0，如果是，那么还需要减去这种情况的贡献。
我们因而可以得到 \(O(n\log_2(\max a))\) 的算法。
小结：
- 注意推导 \(f\) 过程中，调整类似的推导来解决当前问题的方法！
- 熟悉一下求 \(\bmod 2\) 意义下方程解的个数的方法。
- 不要害怕分类讨论??；
代码
#include <cstdio>
#include <algorithm>
#define rep( i, a, b ) for( int i = (a) ; i <= (b) ; i ++ )
#define per( i, a, b ) for( int i = (a) ; i >= (b) ; i -- )
typedef long long LL;
const int mod = 1e9 + 7;
const int MAXN = 1e5 + 5, MAXLOG = 65;
template<typename _T>
void read( _T &x )
{
x = 0; char s = getchar(); int f = 1;
while( ! ( ‘0‘ <= s && s <= ‘9‘ ) ) { f = 1; if( s == ‘-‘ ) f = -1; s = getchar(); }
while( ‘0‘ <= s && s <= ‘9‘ ) { x = ( x << 3 ) + ( x << 1 ) + ( s - ‘0‘ ), s = getchar(); }
x *= f;
}
template<typename _T>
void write( _T x )
{
if( x < 0 ) putchar( ‘-‘ ), x = -x;
if( 9 < x ) write( x / 10 );
putchar( x % 10 + ‘0‘ );
}
LL bas[MAXN]; int siz = 0;
LL A[MAXN], pref[MAXN], suf[MAXN];
int pw[MAXN];
int N;
inline int Mul( int x, int v ) { return 1ll * x * v % mod; }
inline int Sub( int x, int v ) { return ( x -= v ) < 0 ? x + mod : x; }
inline int Add( int x, int v ) { return ( x += v ) >= mod ? x - mod : x; }
void Insert( LL v )
{
per( i, 59, 0 )
{
if( ! ( v >> i & 1 ) ) continue;
if( ! bas[i] ) { bas[i] = v, siz ++; break; }
v ^= bas[i];
}
}
bool Chk( LL v )
{
per( i, 59, 0 )
{
if( ! ( v >> i & 1 ) ) continue;
if( ! bas[i] ) return false; v ^= bas[i];
}
return true;
}
int main()
{
read( N );
rep( i, 1, N ) read( A[i] );
std :: sort( A + 1, A + 1 + N );
per( i, N, 1 ) suf[i] = suf[i + 1] ^ A[i];
rep( i, 1, N ) pref[i] = pref[i - 1] ^ A[i];
pw[0] = 1; rep( i, 1, N ) pw[i] = Mul( pw[i - 1], 2 );
int ans = pref[N] == 0;
for( int i = N, j ; i ; i = j )
{
for( j = i ; j && A[j] == A[i] ; j -- );
int odd = pw[i - j - 1], eve = Sub( pw[i - j - 1], 1 );
// if a_i is the largest black ones
LL val = A[i] ^ ( ( ( i - j ) % 2 == 0 ) * A[i] ) ^ pref[j] ^ suf[i + 1];
if( val == 0 ) ans = Add( ans, odd );
val = ( A[i] - 1 ) ^ ( ( ( i - j ) % 2 == 1 ) * A[i] ) ^ pref[j] ^ suf[i + 1];
if( val == 0 ) ans = Add( ans, eve );
// if a_i is not the largest black ones
val = ( A[i] - 1 ) ^ ( ( ( i - j ) % 2 == 0 ) * A[i] ) ^ pref[j];
if( Chk( val ) )
{
ans = Add( ans, Mul( odd, pw[N - i - siz] ) );
if( ! ( val ^ suf[i + 1] ) ) ans = Sub( ans, odd );
}
val = A[i] ^ ( ( ( i - j ) % 2 == 1 ) * A[i] ) ^ pref[j];
if( Chk( val ) )
{
ans = Add( ans, Mul( eve, pw[N - i - siz] ) );
if( ! ( val ^ suf[i + 1] ) ) ans = Sub( ans, eve );
}
Insert( A[i] );
}
write( ans ), putchar( ‘\n‘ );
return 0;
}