Overview

This is a Sprague-Grundy theorem problem where we view the stones on each vertex as pieces on a directed acyclic graph (DAG). We need to count the number of target vertices such that if Takahashi (the first player) optimally performs the operation “remove all stones on one vertex” before the game starts, he can win.

Analysis

Game Properties

In this game, each stone behaves independently of other stones as a piece “moving along the arrows of the vertices”. Since the arrows always point from a vertex with a larger index to a vertex with a smaller index (\(U_j > V_j\)), the graph is a finite directed acyclic graph (DAG), and the game is guaranteed to terminate.

Such an impartial game can be analyzed using the Sprague-Grundy theorem. For each vertex \(i\), we define the Grundy value \(g_i\) as follows:

\[g_i = \mathrm{mex}\{\, g_v \mid \text{there is an arrow from } i \text{ to } v\,\}\]

Here, \(\mathrm{mex}(S)\) is the minimum non-negative integer not contained in the set \(S\). For vertices with no outgoing arrows, \(g_i = 0\).

Determining the Winner of the Entire Board

Since the entire board is the sum of “independent games for each stone”, the win/loss is determined by the XOR sum of the Grundy values. Since vertex \(i\) has \(A_i\) stones and each contributes \(g_i\), we XOR \(g_i\) a total of \(A_i\) times.

Here is an important observation: - If \(A_i\) is even, \(g_i \oplus g_i \oplus \cdots = 0\) (no contribution). - If \(A_i\) is odd, the contribution is \(g_i\).

Thus, the XOR sum of the entire board is:

\[X = \bigoplus_{i: A_i \text{ is odd}} g_i\]

And if \(X \neq 0\), the first player (the player whose turn it is) wins, while if \(X = 0\), the first player loses.

Effect of the Removal Operation

Takahashi removes all stones on a certain vertex \(i\) (\(A_i \to 0\)) exactly once before the game begins. We need to count the number of vertices such that the board after removal is a winning state for the first player (= Takahashi), i.e., the XOR sum is non-zero.

Removing the stones on vertex \(i\) makes \(A_i\) even (\(0\)). - If \(A_i\) was originally odd: The contribution \(g_i\) disappears, so the XOR sum after removal becomes \(X \oplus g_i\). Takahashi wins if this is not \(0\). The condition is \(g_i \neq X\). - If \(A_i\) was originally even: Since it originally contributed \(0\), the XOR sum after removal remains \(X\). Takahashi wins if this is not \(0\). The condition is \(X \neq 0\) (all even vertices become valid targets).

Counting these vertices gives the answer.

Algorithm

1. Calculating Grundy Values: Since the arrows always point from a larger-indexed vertex to a smaller-indexed vertex, if we process them in the order \(i = 1, 2, \ldots, N\), the destination Grundy values \(g_v\) (\(v < i\)) required to calculate \(g_i\) will already have been computed. For each vertex, we insert the Grundy values of its destinations into a set and find the mex.

2. Calculating the Overall XOR Sum \(X\): We XOR \(g_i\) for all vertices where \(A_i\) is odd. At the same time, we count the number of vertices where \(A_i\) is even, denoted as even_count.

3. Counting the Answer:

   • If \(X \neq 0\), add the count of even vertices even_count.
   • Add the number of odd vertices that satisfy \(g_i \neq X\).

Explanation of the Condition

For example, the condition \(g_i \neq X\) might not be immediately intuitive, but it elegantly combines both of the following cases: - If “currently \(X \neq 0\) (Takahashi would win even without doing anything)”, we just need to choose \(g_i\) such that we can maintain \(X \oplus g_i \neq 0\) after removal. - If “currently \(X = 0\) (he would lose otherwise)”, we can remove a vertex with \(g_i \neq 0\) to make \(X \oplus g_i \neq 0\).

Complexity

• Time Complexity: \(O(N + M)\)
  • In the Grundy value calculation, each edge is traversed exactly once, and the overall mex calculation is proportional to the number of edges.
• Space Complexity: \(O(N + M)\)

Implementation Details

• Parity Check of \(A_i\): Although \(A_i\) can be up to \(10^9\), we only need its parity. In the code, by reading the input as a byte string and checking the least significant bit of the last character (byte) of the string representation of the number (a[-1] & 1), we can quickly determine the parity while avoiding expensive conversion to large integers (this optimization is effective since \(N \leq 10^6\)).

• Calculating mex: We insert the Grundy values of the destinations into a set s, and search for the “minimum value not contained in the set” starting from \(0\). This is efficient because the Grundy value of a vertex is bounded by its out-degree.

• Fast I/O: Since \(N\) can be as large as \(10^6\), we speed up I/O by reading the input all at once using sys.stdin.buffer.read() and then splitting it for processing.

  Source Code

import sys

def main():
    data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(data[idx]); idx += 1
    M = int(data[idx]); idx += 1
    A = data[idx:idx+N]; idx += N

    adj = {}
    for _ in range(M):
        u = int(data[idx]); idx += 1
        v = int(data[idx]); idx += 1
        if u in adj:
            adj[u].append(v)
        else:
            adj[u] = [v]

    g = [0] * (N + 1)
    for i in range(1, N + 1):
        lst = adj.get(i)
        if lst:
            s = set()
            for v in lst:
                s.add(g[v])
            m = 0
            while m in s:
                m += 1
            g[i] = m

    # compute total XOR over odd cells
    X = 0
    even_count = 0
    for i in range(1, N + 1):
        a = A[i-1]
        if a[-1] & 1:  # odd number
            X ^= g[i]
        else:
            even_count += 1

    ans = 0
    if X != 0:
        ans += even_count
    for i in range(1, N + 1):
        a = A[i-1]
        if a[-1] & 1:
            if g[i] != X:
                ans += 1

    print(ans)

main()

---

This editorial was generated by claude4.8opus-high.