Cauchy-Schwarz の不等式より、非負実数 \(\{x_i\}, \{y_i\}\) に対して

\[\left( \sum_i^N x_i \right) \left( \sum_i^N y_i \right) \geq \left( \sum_i^N \sqrt{x_i y_i} \right)^2\]

が成り立ち、等号は \(y_i\) がすべて \(0\) のとき、あるいは \(x_1 / y_1 = \dots = x_N / y_N \) のときに成り立ちます。

\(A_i, A_{i+1}, \dots, A_{i+M-1}, B_1, \dots, B_M\) がすべて非零の場合、上に述べた Cauchy-Schwarz の不等式およびその等号成立条件より、各 \(j\) に対し \(A_{i+j-1} = t B_j\) なる \(t\) が存在することは、

\[ \left( \sum_j^N A_{i+j-1}/B_j \right) \left( \sum_j^N B_j/A_{i+j-1} \right) = N^2\]

と同値であることがわかります。

\(A_i, B_i\) が \(0\) を含む場合を考えます。\(f(x,y)\) を \(y=0\) のとき \(0\)、\(y\neq 0\) のとき \(x/y\) なる関数とすると、\(i\) が問題の条件を満たすことは

\[ \left( \sum_j^N f(A_{i+j-1}, B_j) \right) \left( \sum_j^N f(B_j, A_{i+j-1}) \right) = \left( \sum_i ^N \mathbf{1}(A_{i+j-1} \neq 0 \wedge B_j \neq 0)\right)^2\]

と同値であることがわかります。右辺は各要素 \(0\) に対しては \(0\)、\(0\) 以外に対しては \(1\) として作った数列の畳み込みを考えることで計算可能です。 左辺は、\(0^{-1} = 0\) とみなした上で \(\{ A_i \}, \{ {B_i}^{-1} \}\) の畳み込み、および \(\{ B_i \}, \{ {A_i}^{-1} \}\) の畳み込みを考えることで計算可能です。実際には \(x^{-1}\) の計算は適当な素数 \(p\) をとって \(\mathrm{mod} p\) での逆元を考えることにして、様々な \(p\) に対して考えるとよいです（なお、実際には 998244353 だけを考えれば通りました）

この解法は \(O(N)\) の長さの畳み込みを行うため計算量は \(O(N \log N)\) となります。