Overview

This is an independent game where each stone moves along the arrows to a square with a smaller index.
We can determine the winner by finding the Grundy value of each square and checking whether the overall XOR sum is non-zero.

Analysis

This game is an impartial game with multiple stones.
Since each stone does not affect other stones and simply moves from its current square along the arrows, we can treat each stone as an independent game.

Considering a Single Stone

Suppose there is a single stone on square \(u\).
This stone can be moved to square \(v\) by choosing an arrow \((u, v)\) starting from \(u\).

In such a game, we can define the Grundy value \(g_u\) for each square \(u\):

\[ g_u = \mathrm{mex}\{ g_v \mid \text{there is an arrow } u \to v \} \]

Here, \(\mathrm{mex}\) is the “minimum excludant” (the smallest non-negative integer not contained in the set).

For example, if the Grundy values of the reachable squares are \(\{0, 1, 3\}\), the mex is \(2\).

Since all arrows always point from a larger index to a smaller index (\(U_j > V_j\)), if we process the squares in order starting from square \(1\), the Grundy values of the reachable squares will already have been calculated.

When There Are Multiple Stones

For a combination of multiple independent games, by the Sprague-Grundy theorem, the overall state can be represented by the XOR sum of the Grundy values of all stones.

That is, if we let the overall XOR sum be \(X\):

• If \(X = 0\), the second player wins.
• If \(X \neq 0\), the first player wins.

Suppose there are \(A_i\) stones on square \(i\), and its Grundy value is \(g_i\).
The contribution from this square is:

\[ \underbrace{g_i \oplus g_i \oplus \cdots \oplus g_i}_{A_i \text{ times}} \]

Since XORing the same value twice cancels it out:

• If \(A_i\) is even, the contribution is \(0\).
• If \(A_i\) is odd, the contribution is \(g_i\).

Therefore, it is sufficient to only consider the parity of the number of stones.

The XOR sum of the initial state is:

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

Effect of Removal

Before starting the game, we remove all stones on square \(i\).

At this point, the contribution of square \(i\) disappears from the overall XOR sum.

• If \(A_i\) is even, the original contribution was \(0\), so the XOR sum does not change.
• If \(A_i\) is odd, the contribution \(g_i\) disappears, so the XOR sum becomes \(X \oplus g_i\).

Thus, the XOR sum \(X_i\) after removing the stones on square \(i\) is:

\[ X_i = \begin{cases} X \oplus g_i & (A_i \text{ is odd}) \\ X & (A_i \text{ is even}) \end{cases} \]

Takahashi can win if the XOR sum after removal is non-zero.
Therefore, we just need to check if \(X_i \neq 0\) for each square \(i\).

Naively recalculating the entire game for each removal candidate would take \(O(N(N+M))\) time, which is too slow for \(N \leq 10^6\).
However, if we calculate the Grundy values and the initial XOR sum only once, the check for each square can be done in \(O(1)\) time.

Algorithm

1. Store only the parity of each \(A_i\).
2. Represent the arrows using an adjacency list.
3. Calculate the Grundy values in ascending order of the square indices.
   • Since arrows point from larger indices to smaller indices, when processing square \(u\), the Grundy values of the reachable squares \(v\) are already known.
   • Collect the Grundy values of the reachable squares and set \(g_u\) to their mex.
4. If \(A_i\) is odd, XOR \(g_i\) to the initial XOR sum \(X\).
5. For each square \(i\), find the XOR sum after removal:
   • If \(A_i\) is odd: \(X \oplus g_i\)
   • If \(A_i\) is even: \(X\)
6. Count the number of squares where the XOR sum after removal is non-zero.

Complexity

• Time Complexity: \(O(N + M)\)
• Space Complexity: \(O(N + M)\)

Key Implementation Points

In calculating the Grundy values, we need to find the mex quickly.

Initializing an array for each square is too slow, so we use a seen array and a stamp variable.

++stamp;

for (int e = head[u]; e != -1; e = nxt[e]) {
    int g = grundy[to[e]];
    seen[g] = stamp;
}

int mex = 0;
while (seen[mex] == stamp) mex++;

This way, we do not need to initialize the entire seen array every time.

Also, the Grundy value of square \(u\) is at most its out-degree \(d\). Thus, the total time complexity remains within \(O(N+M)\).

Source Code

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

class FastScanner {
    static constexpr int BUFSIZE = 1 << 20;
    int idx = 0, size = 0;
    char buf[BUFSIZE];

    char getChar() {
        if (idx >= size) {
            size = (int)fread(buf, 1, BUFSIZE, stdin);
            idx = 0;
            if (size == 0) return '\0';
        }
        return buf[idx++];
    }

public:
    template <class T>
    bool read(T &out) {
        char c;
        T sign = 1;
        T num = 0;

        c = getChar();
        if (c == '\0') return false;

        while (c != '-' && (c < '0' || c > '9')) {
            c = getChar();
            if (c == '\0') return false;
        }

        if (c == '-') {
            sign = -1;
            c = getChar();
        }

        while (c >= '0' && c <= '9') {
            num = num * 10 + (c - '0');
            c = getChar();
        }

        out = num * sign;
        return true;
    }
};

int main() {
    FastScanner fs;

    int N, M;
    fs.read(N);
    fs.read(M);

    vector<unsigned char> odd(N + 1);
    for (int i = 1; i <= N; i++) {
        long long x;
        fs.read(x);
        odd[i] = (unsigned char)(x & 1);
    }

    vector<int> head(N + 1, -1);
    vector<int> to(M), nxt(M);

    for (int e = 0; e < M; e++) {
        int U, V;
        fs.read(U);
        fs.read(V);
        to[e] = V;
        nxt[e] = head[U];
        head[U] = e;
    }

    vector<int> grundy(N + 1, 0);
    vector<int> seen(M + 2, 0);
    int stamp = 0;

    int xr = 0;

    for (int u = 1; u <= N; u++) {
        ++stamp;

        for (int e = head[u]; e != -1; e = nxt[e]) {
            int g = grundy[to[e]];
            if (g <= M) seen[g] = stamp;
        }

        int mex = 0;
        while (seen[mex] == stamp) mex++;

        grundy[u] = mex;

        if (odd[u]) xr ^= mex;
    }

    long long ans = 0;
    for (int i = 1; i <= N; i++) {
        int after = xr;
        if (odd[i]) after ^= grundy[i];
        if (after != 0) ans++;
    }

    printf("%lld\n", ans);
    return 0;
}

---

This editorial was generated by gpt-5.5-high.