先想办法表示出 $\prod \limits_{i = l} ^ r a_i$ 的值。设 $p_i$ 表示 $[0,i]$ 的前缀积，则子段 $[l,r]$ 的乘积为 $\frac{p_r}{p_{l - 1}}$。由于 $a_i \in \{-1,1\}$，则 $\prod \limits_{i = l}^r a_i = \frac{p_r}{p_{l - 1}} = p_r \times p_{l - 1}$（因此设 $p_0 = 1$）。
令 $C_1$ 为 $p_0, p_1, \dots, p_n$ 中 $1$ 的个数，$C_{-1}$ 为 $-1$ 的个数。显然 $C_1 + C_{-1} = n + 1$。容易发现，只有当 $p_j$ 和 $p_{i-1}$ 符号相同时，乘积为 $1$；符号不同时，乘积为 $-1$。所以说乘积为 $1$ 的子段数量是 $\binom{C_1}{2} + \binom{C_{-1}}{2}$，而乘积为 $-1$ 的子段数量是 $C_1 \times C_{-1}$。由题目要求可知，所有子段乘积之和为 $k$，即 $k = \binom{C_1}{2} + \binom{C_{-1}}{2} - C_1 \times C_{-1} = \dfrac{(C_1 - C_{-1})^2 - (n + 1)}{2}$。移项可知，$C_1 - C_{-1} = \pm \sqrt{2k + n + 1}$。又因为 $C_1 + C_{-1} = n + 1$，所以 $C_1 = \dfrac{n + 1 \pm \sqrt{2k + n + 1}}{2}$。
接下来考虑处理 $[l,r]$ 的重排。显然对这一区间进行重排不会影响 $p_0 \sim p_{l - 1}$ 和 $p_{r + 1} \sim p_n$ 的值。而该区间内 $p_i$ 的改变只会受到 $a_i = -1, \quad i \in [l,r]$ 的位置的影响，而这些 $a_i = -1$ 的位置所对应的 $p_i$ 的值是 $\pm 1$（或者 $\mp 1$，具体受到 $p_{l - 1}$ 的值的影响），因此 $a_i = -1$ 所对应的 $p_i$ 均为定值，题目转化为求重排 $a_i = 1, \quad i \in [l,r]$ 使得满足 $C_1 = \dfrac{n + 1 \pm \sqrt{2k + n + 1}}{2}$。
设 $x$ 为 $[l,r]$ 中 $a_i = 1$ 的个数，$y$ 为 $[l,r]$ 中 $a_i = -1$ 的个数，则 $x + y = r - l + 1$。设 $C_1’$ 表示在该区间中 $a_i = 1$ 的位置上需要 $p_i$ 的值为 $1$ 的个数，而 $y$ 个 $a_i = -1$ 的位置相当于隔板，将 $a_i = 1$ 的段分为 $l_0,l_1,\ldots,l_y$ 共 $y + 1$ 的段。奇数块和偶数块的 $p_i$ 的值相反，所以可以转化为小球放入盒中的问题。假设 $l_0$ 对应的段为 $p_i = 1$，则相当于是将这 $C_1’$ 个小球放入 $\lfloor \frac{y}{2} \rfloor + 1$ 个盒子中，盒子可以为空；将剩余的 $x - C_1’$ 个小球放入 $\lfloor \frac{y + 1}{2} \rfloor$ 个盒子中，盒子可以为空。方案数为：
由于题目说每个数均认为不相同，因此最后答案需要在乘上 $x! \times y!$。注意特判 $0$ 个小球放入 $0$ 个盒子的情况，此时方案数为 $1$。
注意到 $C_1$ 的值可能为 $\dfrac{n + 1 + \sqrt{2k + n + 1}}{2}$ 或 $\dfrac{n + 1 - \sqrt{2k + n + 1}}{2}$，因此需要枚举两种情况（$\Delta = 0$ 时为一种情况），但需要考虑增根的情况，即 $2k + n + 1 < 0$ 或 $2k + n + 1$ 不是完全平方数的情况，此时答案为 $0$。
最后的代码如下：
1 | void solve() |
