hackercupai/hackercup huggingface dataset:
Another way to think of the hash is partitioning the array \(A\) into segments, choosing only a subset of segments to XOR together for a hash.

Consider a dynamic programming approach where we build a table \(dp(i, x)\) storing whether it's possible to attain an XOR value of \(x\) by choosing a set of non-overlapping subarrays in \(A_{1..i}\). We initialize \(dp(0, 0)\) as true (no orders \(\to\) hash \(0\)). For each true \(d(i, x)\), we'll consider each \(j > i\), corresponding to segment \(A_{(i+1)..j}\). We can either choose to exclude this segment (not changing \(x\)) and set \(dp(j, x)\) to true, or include it and set \(dp(j, x \oplus [(A_{i+1} + ... + A_j) \text{ mod } M])\) to true. In the end, we want to output the number of \(x\)'s where \(d(N, x)\) is true.

We can first pre-compute a modded prefix sum array on \(A\), allowing us to later obtain the deliciousness of any range in constant time. However, the number of states in the approach above is \(\mathcal{O}(N)\) times the \(\mathcal{O}(M)\) possible XOR values. Transitioning adds another factor of \(N\), for an overall running time of \(\mathcal{O}(N^2 M)\), which won't be fast enough.

Instead, let's imagine starting with a hash \(x = 0\), and repeatedly transitioning \(x\) to \(x \oplus d\) by applying a deliciousness score \(d\) of a segment \(A_{j..k}\) *starting after the minimum* \(i\) such that \(A_{1..i}\) can produce \(x\) (where \(i < j \le k\)). If here are many such segments for a given \(i\), we might as well always choose one with the minimum \(k\), as it will leave us with more options later on. Using \(\mathcal{O}(N^2)\) time, we can precompute a table \(\text{first}[i][d]\) storing the first \(j \ge i\) such that \(A_{i..j}\) yields deliciousness \(d\) (infinity if there's no such \(j\)).

To search the \(\mathcal{O}(M)\) hash space, we will apply an algorithm similar to Dijkstra's, except we'll let the distance array \(\text{dist}[x]\) denote the minimum \(i\) such that \(A_{1..i}\) can produce hash \(x\) (\(\text{dist}[x]\) initialized to infinity). In the main loop, we repeatedly find the unvisited hash \(x\) with minimum \(\text{dist}[x]\), mark it as visited, then consider each deliciousness score \(d = 0..(K-1)\) for which we perform the relaxation of neighbor \(x \oplus d\) as \(\text{dist}[x \oplus d] = \text{min}(\text{dist}[x \oplus d], \text{first}[\text{dist}[x]][d])\).

In the end, we report the number of hashes \(x\) with non-infinite \(\text{dist}[x]\). Analogous to quadratic Dijkstra, with \(\mathcal{O}(M)\) states we get an algorithm that runs in time \(\mathcal{O}(M^2)\).