Overview

This is a two-player game played by moving stones on a DAG (directed acyclic graph), and we determine the winner using the Sprague–Grundy theorem (Nim theory). We count the number of squares such that Takahashi can win by performing the “removal” operation exactly once.

Analysis

Understanding the Game’s Essence with Grundy Numbers

Since the arrows always point from a square with a larger index to a square with a smaller index (\(U_j > V_j\)), moving the stones will never return them to the same square, and the game is guaranteed to terminate. The player who cannot make a move loses (normal play convention).

This game can be viewed as the “direct sum of games” where each stone moves independently. Let \(g[i]\) be the Grundy number of the state where a single stone is placed on square \(i\). It can be found using the following recurrence relation:

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

Here, \(\mathrm{mex}(S)\) is the minimum non-negative integer not contained in the set \(S\). Since no arrows go out of squares with \(0\) out-degree, we cannot operate on them, so \(g[i] = 0\).

Multiple Stones and Parity

There are \(A_i\) stones on square \(i\). Since all stones on the same square have the same Grundy number \(g[i]\), their contribution to the Grundy number (XOR sum) of the direct sum is:

\[\underbrace{g[i] \oplus g[i] \oplus \cdots \oplus g[i]}_{A_i \text{ stones}}\]

XORing the same value an even number of times results in \(0\), and an odd number of times results in \(g[i]\), so:

• If \(A_i\) is even, the contribution is \(0\).
• If \(A_i\) is odd, the contribution is \(g[i]\).

In other words, the Grundy number of the entire board is:

\[\text{total} = \bigoplus_{i:\, A_i \text{ is odd}} g[i]\]

and the first player (Takahashi) wins if and only if \(\text{total} \neq 0\).

Effect of the Removal Operation

Takahashi removes all stones from a certain square \(i\) exactly once (\(A_i \to 0\)). Since \(0\) is even, the parity after removal becomes “even”. We analyze how the XOR sum changes depending on the cases:

• Removing from a square where \(A_i\) was originally even: The contribution was originally \(0\), and it remains \(0\) after removal. The XOR sum remains \(\text{total}\). \(\to\) The winning condition is \(\text{total} \neq 0\).
• Removing from a square where \(A_i\) was originally odd: The contribution \(g[i]\) disappears, so the new XOR sum is \(\text{total} \oplus g[i]\). \(\to\) The winning condition is \(\text{total} \oplus g[i] \neq 0\), which is \(g[i] \neq \text{total}\).

Counting the number of squares that satisfy these conditions gives the answer.

Pitfalls of a Naive Implementation

Since \(N\) is up to \(10^6\) and \(A_i\) is up to \(10^9\), it is impossible to simulate the stones one by one. However, as described above, only the parity of \(A_i\) matters, so it is sufficient to keep only the parity information when reading each \(A_i\).

Algorithm

1. Record the parity of each \(A_i\) and count the number of even squares cntEven.
2. Store the arrows in CSR format (a format that packs the adjacency list into a single array). Since \(V_j < U_j\), if we calculate \(g\) in ascending order of square indices, the referenced \(g[v]\) will already be determined.
3. For each square \(u\), let \(d\) be the out-degree. Only \(g[v]\) values less than or equal to \(d\) affect the \(\mathrm{mex}\) (since \(\mathrm{mex}\) is at most \(d\)). Utilizing this, we can compute \(\mathrm{mex}\) in \(O(d)\) using a flag array.
4. XOR \(g[i]\) for squares where \(A_i\) is odd to find \(\text{total}\).
5. Aggregate the answer according to the case analysis above.
   • If \(\text{total} \neq 0\), add all even squares (cntEven).
   • Add odd squares where \(g[i] \neq \text{total}\).

Optimization of mex Computation

When finding \(\mathrm{mex}\), clearing the flag array to \(0\) every time may take \(O(N \cdot \text{maxdeg})\) time. Therefore, we can:

• Only set flags for \(g[v]\) values that are less than or equal to \(d\).
• After the computation, traverse the same outgoing edges again to reset only the flags that were set.

By doing this, the processing of each square takes \(O(d)\) time proportional to its out-degree, resulting in \(O(M)\) overall.

Complexity

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

Implementation Points

• Since \(A_i \le 10^9\), we can read them as 64-bit integers and save memory by storing only the parity (a & 1) (\(N \le 10^6\)).

• Storing the arrows using CSR (creating offsets with prefix sums) is advantageous in terms of both memory and speed compared to having \(N\) std::vectors for adjacency lists.

• If we compute \(g\) in ascending order from square \(1\) to \(N\), the constraint \(V_j < U_j\) guarantees that the referenced values have already been computed.

• It is sufficient to allocate the flag array for \(\mathrm{mex}\) up to the maximum out-degree \(+ 2\). Any \(g[v]\) value exceeding the out-degree does not affect the \(\mathrm{mex}\), so it can be ignored.

• Since the input size is large, using fast I/O (such as custom buffer reading) is safe.

  Source Code

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

static char buf[1 << 25];
int bufpos = 0, buflen = 0;
inline int readChar() {
    if (bufpos == buflen) {
        buflen = (int)fread(buf, 1, sizeof(buf), stdin);
        bufpos = 0;
        if (buflen == 0) return -1;
    }
    return buf[bufpos++];
}
inline long long readInt() {
    int c = readChar();
    while (c != '-' && (c < '0' || c > '9')) c = readChar();
    bool neg = false;
    if (c == '-') { neg = true; c = readChar(); }
    long long x = 0;
    while (c >= '0' && c <= '9') { x = x * 10 + (c - '0'); c = readChar(); }
    return neg ? -x : x;
}

int main() {
    int N = (int)readInt();
    int M = (int)readInt();

    vector<char> parity(N + 1, 0); // A_i の偶奇
    int cntEven = 0;
    for (int i = 1; i <= N; i++) {
        long long a = readInt();
        if (a & 1LL) parity[i] = 1;
        else cntEven++;
    }

    // 出辺の格納（CSR）
    vector<int> U(M), V(M);
    vector<int> deg(N + 2, 0);
    for (int j = 0; j < M; j++) {
        int u = (int)readInt();
        int v = (int)readInt();
        U[j] = u; V[j] = v;
        deg[u]++;
    }
    vector<int> start(N + 2, 0);
    for (int i = 1; i <= N + 1; i++) start[i] = start[i - 1] + deg[i - 1];
    // start[i] は CSR の開始位置（マス i は start[i]..start[i+1]）
    vector<int> adj(M);
    {
        vector<int> pos(N + 2);
        for (int i = 0; i <= N + 1; i++) pos[i] = start[i];
        for (int j = 0; j < M; j++) {
            int u = U[j];
            adj[pos[u]++] = V[j];
        }
    }

    vector<int> g(N + 1, 0);
    // mex 用の作業領域
    vector<int> markVal; // 訪問したインデックス
    vector<char> mark;   // mex用フラグ
    // mark は最大次数+1 まで使う。動的に確保。
    int maxdeg = 0;
    for (int i = 1; i <= N; i++) maxdeg = max(maxdeg, deg[i]);
    mark.assign(maxdeg + 2, 0);

    for (int u = 1; u <= N; u++) {
        int s = start[u], e = start[u + 1];
        if (s == e) { g[u] = 0; continue; }
        int d = e - s;
        // 値が d 以下のものだけ mex に影響
        for (int k = s; k < e; k++) {
            int gv = g[adj[k]];
            if (gv <= d) mark[gv] = 1;
        }
        int m = 0;
        while (m <= d && mark[m]) m++;
        g[u] = m;
        // リセット
        for (int k = s; k < e; k++) {
            int gv = g[adj[k]];
            if (gv <= d) mark[gv] = 0;
        }
    }

    // total XOR （A_i が奇数のマスの g[i] の XOR）
    long long total = 0;
    for (int i = 1; i <= N; i++) {
        if (parity[i]) total ^= g[i];
    }

    long long ans = 0;
    // 偶数マス：除去後 XOR は total
    if (total != 0) ans += cntEven;
    // 奇数マス：除去後 XOR は total ^ g[i]
    for (int i = 1; i <= N; i++) {
        if (parity[i]) {
            if ((long long)g[i] != total) ans++;
        }
    }

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

---

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