If \(e_i = 1\) or \(e_i = 2\)

First, we consider how to solve it if there is no condition such that \(e_i=0\). Then, it is no use using \(0\) as an element of \(X\), so we can assume that all elements are \(1\) or \(2\). Considering the product of some \(1\)’s and \(2\)’s, it turns out that the product is \(1\) if there is an even number of \(2\)’s, and \(2\) if odd.
Therefore, let us define \(y_{i,j}\) as follows:

• \(y_{i,j}=0\) if \(x_{i,j}=1\) and \(y_{i,j}=1\) if \(x_{i,j}=2\).

Considering the same way for the variables \(e_i\) representing the conditions, the problem is boiled down to a simultaneous equations on \(F_2\) of \(N^2\) variables. (If the system does not have a solution, the answer is No.) A system of linear equations on \(F_2\) with \(A\) variables and \(B\) equations can be solved in a total of \(\mathrm {O}(\frac{AB^2}{w})\) time (where \(w\) is the word size) by Gaussian elimination using bitsets. However, it is not fast enough for \(A=N^2\) and \(B=Q\). Instead, we may use the trick of two-dimensional cumulative sum to eliminate the number of variables to \(4Q\) to make it fast enough.

Solution to the original problem

Even if there is a condition with \(e_i=0\), the elements covered by the conditions with \(e_i=1,2\) cannot be \(0\). Meanwhile, we can freely let an element \(0\) if it is not covered by the conditions with \(e_i=1,2\). Hence, it is valid to first construct \(X\) as mentioned above based only on the conditions with \(e_i=1,2\), and then letting the elements not covered by such condition \(0\). (If it results in violating a condition with \(e_i=0\), then the answer is No.)