Problem: hash_slinger (2023 round3)

Spongebob wants to go out trick-or-treating on Halloween, but has to work a graveyard shift at the Krusty Krab. Luckily, his ghostly fry cook friend, the hash-slinging slasher, is here to cover.

At the start of the shift, there are \(N\) patties on the grill (numbered from \(1\) to \(N\)), the \(i\)th of which weighs \(A_i\) grams. For each order that comes in, the slasher removes from the grill a non-empty sequence of patties at contiguous indices \(i..j\) (patties \(i..j\) must all be on the grill at that moment). The *deliciousness* of the order is defined as \((A_i + ... + A_j)\), modulo \(M\) because too much meat can be overpowering! Note that if a patty is removed, a future order's range cannot span across that empty spot. Also, there may be patties left over at the end.

As proof of his hard work at the end of the shift, the slasher will compute a hash by taking the [bitwise XOR](https://en.wikipedia.org/wiki/Bitwise_operation) of the deliciousnesses of all the orders. How many distinct hashes are possible across all valid sequences of \(0\) or more orders?


# Constraints

\(1 \leq T \leq 125\)
\(0 \leq A_i \leq 1{,}000{,}000{,}000\)
\(1 \leq N \leq 9{,}000\)
\(1 \leq M \leq 5{,}000\)

The sum of \(N + M\) across all test cases is at most \(200{,}000\).


# Input Format

Input begins with an integer \(T\), the number of test cases. Each case begins with a line containing the two integers \(N\) and \(M\). Then, there is a single line containing \(N\) integers, \(A_1, ..., A_N\).


# Output Format

For the \(i\)th test case, print "`Case #i:` " followed by the number of different possible hashes.


# Sample Explanation

In the first sample case, there are \(3\) patties with \(A = [2, 2, 0]\) and \(M = 10\). The possible valid order sequences (patties removed) and hashes are:

- No patties removed \(\to\) hash \(0\)
- Patties \(1..1\) \(\to\) hash \(2\)
- Patties \(2..2\) \(\to\) hash \(2\)
- Patties \(3..3\) \(\to\) hash \(0\)
- Patties \(1..2\) \(\to\) hash \(4\)
- Patties \(2..3\) \(\to\) hash \(2\)
- Patties \(1..3\) \(\to\) hash \(4\)
- Patties \(1..1\) and patties \(2..2\) \(\to\) hash \(0\)
- Patties \(1..1\) and patties \(3..3\) \(\to\) hash \(2\)
- Patties \(2..2\) and patties \(3..3\) \(\to\) hash \(2\)
- Patties \(1..1\) and patties \(2..3\) \(\to\) hash \(0\)
- Patties \(1..2\) and patties \(3..3\) \(\to\) hash \(4\)
- Patties \(1..1\), patties \(2..2\), and patties \(3..3\) \(\to\) hash \(0\)

There are \(3\) distinct hashes the slasher can make: \(0\), \(2\), and \(4\).

In the second case, the slasher can make hashes \(0\) (for example, with no orders) and \(1\) (for example, with \(5\) orders, each including one of the patties).





Sample input:
6
3 10
2 2 0
5 2
8 8 4 0 1
4 100
6 3 5 9
8 100
35 53 3 56 58 14 10 61
8 64
48 16 64 16 19 16 32 48
10 10
259051541 65887488 530604911 813205302 907139220 531875291 795733712 135498985 303233570 953669086


Sample output:
Case #1: 3
Case #2: 2
Case #3: 16
Case #4: 128
Case #5: 8
Case #6: 16


Solution: 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)\).


Code: #include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

const int MAX = 1 << 13;

int solve() {
  int N, K;
  cin >> N >> K;
  vector<int> A(N);
  for (int i = 0; i < N; i++) {
    cin >> A[i];
    A[i] %= K;
  }
  vector<int> first_sofar(K, N + 1);
  vector<vector<int>> first(N, vector<int>(K));
  for (int i = N - 1; i >= 0; --i) {
    int d = 0;
    for (int j = i; j < N; ++j) {
      d = (d + A[j]) % K;
      first_sofar[d] = min(first_sofar[d], j + 1);
    }
    first[i] = first_sofar;
  }
  vector<int> dist(MAX, N + 1);
  vector<bool> visit(MAX);
  dist[0] = 0;
  for (;;) {
    int x = -1;
    for (int j = 0; j < MAX; ++j) {
      if (!visit[j] && dist[j] < N && (x == -1 || dist[x] > dist[j])) {
        x = j;
      }
    }
    if (x == -1) {
      break;
    }
    visit[x] = 1;
    for (int d = 0; d < K; d++) {
      dist[x ^ d] = min(dist[x ^ d], first[dist[x]][d]);
    }
  }
  int res = 0;
  for (int i = 0; i < MAX; ++i) {
    res += (dist[i] != N + 1);
  }
  return res;

}

int main() {
  int T;
  cin >> T;
  for (int t = 1; t <= T; t++) {
    cout << "Case #" << t << ": " << solve() << endl;
  }
  return 0;
}