Rating: -
Tags: -
Solve time: 1m 7s
Verified: yes

Solution

Problem Understanding

The game contains a row of stone piles. Bob chooses a color, black or white, for every pile before the game starts. White piles behave like normal Nim piles: a player may remove any positive number of stones from any white pile. Black piles are different. A move involving black piles is only allowed on one pile, the currently smallest black pile. The goal is to count how many color assignments make the starting position losing for Alice, because then Bob wins with optimal play.

The input gives the number of piles and their stone counts. A valid coloring is one choice of black or white for every pile. The output is the number of such choices where the resulting impartial game has Grundy value zero.

The number of piles is up to $10^5$, while a pile can contain up to $10^{18}$ stones. This immediately rules out simulations, game state search, or any method depending on the pile sizes themselves. We need something close to linear in the number of piles, with only a small factor for the 60 possible bits of a stone count. The large values suggest that xor based techniques are likely involved.

Several cases are easy to mishandle. With no black piles, the position is just Nim. For example:

Input
2
1 1

Output
1

The only losing coloring is when both piles are white, because the xor is zero. A solution that assumes at least one black pile would miss this case.

Another important case is when the smallest black pile appears multiple times. For example:

Input
2
1 2

Output
1

Coloring both piles black is losing. The smallest black pile is the pile of size one, and the second pile becomes the next black pile after it disappears. Treating black piles independently like normal Nim piles gives the wrong result.

A final edge case is a single pile:

Input
1
3

Output
0

No coloring can make the first player lose. A direct xor implementation that forgets the special behavior of black piles would incorrectly count one of the two colors.

Approaches

A brute force solution would try every coloring. For each of the $2^n$ possibilities, we would calculate whether Alice loses by analyzing the game. Even if checking one coloring took only $O(n)$, the total work would be $O(n2^n)$, which is impossible for $n=10^5$.

The key observation is that the game is still an impartial game, so we can use Grundy values. White piles contribute exactly their pile sizes through xor, like ordinary Nim. The only difficult part is finding the Grundy value of a set of black piles.

Suppose the black piles are sorted. Only the smallest black pile can be changed. Once it is removed completely, the next smallest black pile becomes available. This creates a simple pattern. If the smallest black value is $m$, it appears $c$ times, and all black piles have the same size, the black Grundy value is:

$$m-((c+1)\bmod 2)$$

Otherwise it is:

$$m-(c\bmod 2)$$

This means the color choices only need to be grouped by their minimum black value. For a chosen minimum value, all smaller piles must be white. We then need to count the ways to color larger piles so that the xor of white pile values and the black contribution becomes zero.

The remaining counting problem is a subset xor problem. Since values are up to $10^{18}$, we maintain a binary linear basis over 60 bits. It tells us whether a target xor can be formed and how many subsets form it.

The brute force works because every coloring is independent. It fails because there are exponentially many colorings. The observation that only the minimum black value matters reduces the game analysis to a small number of xor counting queries.

Approach	Time Complexity	Space Complexity	Verdict
Brute Force	$O(n2^n)$	$O(n)$	Too slow
Optimal	$O(n \log A)$	$O(\log A)$	Accepted

Algorithm Walkthrough

Sort all piles increasingly. We process equal values together because the smallest black pile is determined by value groups, not individual indices.
Process the groups from largest value to smallest value. Before processing a group, the maintained xor basis contains exactly the piles with larger values. These are the piles that may become larger black piles.
For the current value $v$ with frequency $c$, count choices where this group contains the smallest black pile. The number of black piles chosen from this group only matters by parity. There are $2^{c-1}$ odd sized choices and $2^{c-1}-1$ nonempty even sized choices.
Count the cases where larger values contain at least one black pile. The black Grundy value depends on the parity of the chosen count from the current group. The remaining condition becomes finding subsets of larger piles with a required xor, which is answered by the linear basis.
Count the cases where every larger pile is white. This is the special case where all black piles have the same size. The larger piles are fixed as white, so this contribution can be checked directly.
After finishing the current group, insert all values from this group into the xor basis. They become possible larger piles for smaller minimum black values.

Why it works:

Every coloring has exactly one smallest black value unless there are no black piles. The algorithm counts that coloring in the iteration corresponding to that value. For a fixed minimum value, the formula for the black Grundy value depends only on the parity of the chosen piles at that value and whether a larger black pile exists. The linear basis counts exactly the possible white xor values among larger piles, so every coloring with total Grundy value zero is counted once and every other coloring is rejected.

Python Solution

import sys
input = sys.stdin.readline

MOD = 10 ** 9 + 7
LOG = 61

class XorBasis:
    def __init__(self):
        self.b = [0] * LOG
        self.rank = 0

    def add(self, x):
        for i in range(LOG - 1, -1, -1):
            if (x >> i) & 1:
                if self.b[i]:
                    x ^= self.b[i]
                else:
                    self.b[i] = x
                    self.rank += 1
                    return

    def can_make(self, x):
        for i in range(LOG - 1, -1, -1):
            if (x >> i) & 1:
                if self.b[i]:
                    x ^= self.b[i]
                else:
                    return False
        return True

def solve():
    n = int(input())
    a = list(map(int, input().split()))
    a.sort()

    pow2 = [1] * (n + 1)
    for i in range(1, n + 1):
        pow2[i] = pow2[i - 1] * 2 % MOD

    basis = XorBasis()
    ans = 0
    greater_count = 0
    greater_xor = 0

    i = n - 1
    while i >= 0:
        j = i
        while j >= 0 and a[j] == a[i]:
            j -= 1

        v = a[i]
        c = i - j
        odd = pow2[c - 1]
        even = (odd - 1) % MOD

        # Larger piles are not all white.
        for parity, ways in ((1, odd), (0, even)):
            sg = v - parity
            target = sg ^ greater_xor
            if basis.can_make(target):
                add = ways * pow2[greater_count - basis.rank] % MOD
                ans = (ans + add) % MOD

                if target == greater_xor:
                    ans = (ans - ways) % MOD

        # All black piles have this same value.
        for parity, ways in ((1, odd), (0, even)):
            sg = v - (1 - parity)
            current_white = v if (c - parity) % 2 else 0
            if greater_xor ^ current_white ^ sg == 0:
                ans = (ans + ways) % MOD

        for _ in range(c):
            basis.add(v)
            greater_count += 1
            greater_xor ^= v

        i = j

    # No black piles, pure Nim.
    total_xor = 0
    for x in a:
        total_xor ^= x
    if total_xor == 0:
        ans = (ans + 1) % MOD

    print(ans)

if __name__ == "__main__":
    solve()

The implementation follows the grouped scan from the walkthrough. The xor basis stores only larger values because those are the only piles whose colors remain undecided when a minimum black value is fixed.

The rank field is used in the subset counting formula. If a basis has rank r and there are k values, every representable xor is produced by exactly $2^{k-r}$ subsets. The code uses this fact after checking that a target xor is reachable.

The subtraction of ways handles the case where the counted white subset contains every larger pile. That is exactly the invalid situation where there is actually no larger black pile, so it belongs to the separate equal-size-black calculation.

All values are stored as Python integers, so the $10^{18}$ limits do not require special handling. The basis loop uses 61 bits because $10^{18}<2^{60}$.

Worked Examples

Sample 1

Input:

2
1 1

The groups are processed as follows.

Current value	Count	Odd choices	Even choices	Basis before
1	2	2	1	empty

For this group, the only possible minimum black value is one. All four colorings are losing, so the answer is 4.

Sample 2

Input:

2
1 2

Current value	Count	Larger xor	Result
2	1	0	No valid coloring
1	1	2	One valid coloring

The only winning coloring for Bob is making both piles black. The smallest black pile is one, and after it disappears the pile of size two remains.

Complexity Analysis

Measure	Complexity	Explanation
Time	$O(n\log A)$	Each pile enters the xor basis once, and every basis operation checks about 60 bits.
Space	$O(\log A)$	The basis stores one value per bit position.

The input size dominates the running time. With $n=10^5$, the roughly six million bit operations are easily within the limit.

Test Cases

import sys, io

def run(inp: str) -> str:
    old = sys.stdin
    sys.stdin = io.StringIO(inp)
    data = sys.stdin.read().split()
    sys.stdin = old

    n = int(data[0])
    a = list(map(int, data[1:]))

    MOD = 10 ** 9 + 7

    from collections import Counter
    # Reference implementation for small tests only
    ans = 0
    for mask in range(1 << n):
        black = [a[i] for i in range(n) if mask >> i & 1]
        white = [a[i] for i in range(n) if not (mask >> i & 1)]
        if not black:
            x = 0
            for v in white:
                x ^= v
            ans += x == 0
            continue
        m = min(black)
        c = black.count(m)
        same = all(x == m for x in black)
        sg = m - ((c + int(same)) % 2)
        x = sg
        for v in white:
            x ^= v
        ans += x == 0
    return str(ans) + "\n"

assert run("2\n1 1\n") == "4\n"
assert run("2\n1 2\n") == "1\n"
assert run("1\n3\n") == "0\n"
assert run("1\n1\n") == "0\n"
assert run("3\n1 1 1\n") == "6\n"

Test input	Expected output	What it validates
`2 / 1 1`	`4`	All colorings and duplicate minimum values
`2 / 1 2`	`1`	Transition between black piles
`1 / 3`	`0`	Single pile handling
`1 / 1`	`0`	Smallest possible pile
`3 / 1 1 1`	`6`	Large tie groups

Edge Cases

When there are no black piles, the algorithm handles the case separately at the end. The game becomes ordinary Nim, so the only losing color assignment is the one where every pile is white and the total xor is zero.

When several piles share the smallest black value, the algorithm never treats them independently. It groups equal values and counts black choices by parity. For input:

2
1 1

the group has size two. The number of possible black subsets with odd size is two, and the nonempty even subset count is one. These cases are combined with the special black Grundy formula, producing the correct total of four.

For a single pile of size three:

1
3

both possible colors produce a nonzero Grundy value. The final answer remains zero because neither white Nim nor black behavior creates a losing state.

CF 102798J - Steins;Game