My solution uses a pure DP, with a small optimization using NTT. Let \(S=\sum_{j=1}^{N} A_j x_j .\)

We compare \(S\) with \(M\) bit by bit. Suppose we have already processed the lowest \(i\) bits of both \(S\) and \(M\). Let \(\text{sign}\in\{0,1\}\) indicate the current comparison result: \(\text{sign}=0\) means “\(S\le M\) so far”, and \(\text{sign}=1\) means “\(S>M\) so far”. Since the lowest \(i\) bits have already been handled, storing them in the state is unnecessary.

Define the DP state \( f_i(\text{sum},\text{sign}), \quad\text{where}\quad \text{sum}=\left\lfloor \frac{S}{2^i}\right\rfloor . \) When transitioning to \(f_{i+1}\), we choose a subset of indices \( I=\{i_1,i_2,\ldots,i_k\} \) to turn on the \(i\)-th bit of each corresponding \(x_{i_j}\). Let \(\text{coef}(s)\) be the number of ways to choose a subset of \(I\) such that the sum of the chosen values equals \(s\).

Define the bit function \( bit(x,i)= \begin{cases} 1, & \text{if the }i \text{-th bit is on} \\ 0, & \text{otherwise.} \end{cases} \)

The transition is \( f_i(\text{sum},\text{sign})\cdot \text{coef}(s) \;\longrightarrow\; f_{i+1}\!\left(\left\lfloor \frac{\text{sum}}{2}\right\rfloor + s,\;\text{newSign}\right). \)

Let \( \text{newSum}=\left\lfloor \frac{\text{sum}}{2}\right\rfloor + s. \) If \(\operatorname{bit}(\text{newSum},i)=\operatorname{bit}(M,i)\), then \(\text{newSign}\) depends on the previous comparison (i.e. keep \(\text{newSign}=\text{sign}\)). Otherwise, \( \text{newSign}=[\operatorname{bit}(\text{newSum},i)>\operatorname{bit}(M,i)\big]. \)

The final answer is \( f_{60}(0,0)+f_{60}(1,0). \) The \(sum\) state is always in range \([0, 2 \times 100^2)\). The current time complexity is \(\mathcal{O}(60\cdot (100^2)^2)\). To optimize the transitions, we use NTT to speed up the convolution.

The final time complexity is \(\mathcal{O}(60 \cdot 100^2 \cdot \log_2 (100^2))\)

My code