Official

H - Incomplete Notes Editorial by hitonanode


For each integer \(i\) satisfying \(1 \le i \le N - M + 1\), we define the function \(f_i(t)\), dependent on the variable \(t\), as follows:

\[ f_i (t) = \sum_{j = 1}^M (A_{i + j - 1} - t B_j)^2 \mathbf{1}(A_{i + j - 1} > 0) \mathbf{1}(B_j > 0). \]

Herein, \(\mathbf{1}(x)\) denotes a function returning \(1\) if the proposition \(x\) is true, and \(0\) if false. For each \(i\), if \(f_i (t) = 0\) has a positive real solution, then this particular \(t\) can be employed to construct the \(B\) and \(C\) satisfying the condition.

The task at hand is to get the explicit form of \(f_i (t)\) for each \(i\). The right-hand side can be reduced to a linear convolution by expanding the square. \(f_i (t)\) becomes a quadratic function of \(t\) for each \(i\), with each term’s coefficient being an integer whose absolute value is no more than \(2.5 \times 10^{17}\). Therefore, convolution can be performed over \(\mathbb{F}_p\) using Number Theoretic Transform (NTT) for several primes \(p\) such as \(p = 119 \times 2^{23} + 1\) or \(p = 441 \times 2^{21} + 1\), followed by the reconstruction of the coefficients of each term of \(f_i (t)\) using algorithms like Garner’s algorithm.

Subsequently, it is sufficient to ascertain the number of \(i\) for which \(f_i(t) = 0\) has a positive real solution (actually, from the definition of \(f_i(t)\), if \(f_i (t) = 0\) has real solutions, then these must be positive repeated roots). This can be achieved either by directly computing the discriminant \(D = b^2 - 4ac\) of the quadratic equation \(f_i(t) = at^2 + bt + c = 0\) using a 128-bit integer type, or by selecting several large primes \(p\) and repetitively calculating \(D\) over \(\mathbb{F}_p\).

The computational bottleneck in the aforementioned solution lies in the convolution of sequences of length \(O(N)\) (anticipated to occur six times), with the expected computational complexity being \(O(N \log N)\).

posted:
last update: