题解

思路

把尚未写入题目的空前缀 $q_0=0$ 也加入多重集合。令 $c_v$ 表示值 $v$ 的出现次数。任何隐藏数组都对应一条从 $0$ 出发、每一步走到相邻整数、访问值 $v$ 恰好 $c_v$ 次的路径。

若某两个出现值之间有空缺，这条路径不可能存在。否则枚举最后的前缀和 $s=q_n$，可以从最大值向最小值逐层恢复必须已有的路径段，并用插板法统计在同一层插入往返段 $(-1,+1)$ 的方案。

设出现值范围为 $[L,R]$。对固定终点 $s$，定义辅助量 $d_v$。从最高层向下递推：

$$d_{R-1}=c_R+[R>0]-[R=s],$$ $$d_v=c_{v+1}-d_{v+1}+[v\ge s]+[v\ge0]\qquad(L-1\le v<R-1).$$

若 $d_{L-1}\ne0$，这个终点不可行。在第 $v$ 层已经有 $d_v$ 个可插入位置，需要补出 $c_v-d_v$ 次访问，插板法给出

$$\binom{c_v-1}{c_v-d_v}.$$

固定 $s$ 的方案数是这些组合数之积，再对全部 $s\in[L,R]$ 求和。

做法

子任务 1：枚举隐藏数组

枚举全部 $2^n$ 个 $\{-1,1\}$ 数组，计算并排序前缀和，与输入逐项比较。复杂度为 $O(2^n n\log n)$。

子任务 2：有界前缀值域

按上述递推计算固定终点的贡献需要 $O(n)$ 时间。若 $p_n-p_1\le20$，可能的终点只有常数个，总复杂度为 $O(n(p_n-p_1+1))=O(n)$。

子任务 3：完整组合计数

完整数据中值域宽度至多 $2n$。枚举每个可能终点并执行线性递推，总复杂度为 $O(n^2)$。预处理阶乘和逆阶乘后，每个组合数可在 $O(1)$ 时间求出。

正确性证明

引理 1

若 $[L,R]$ 内存在某个 $v$ 满足 $c_v=0$，则答案为零。

证明。 路径每一步只能在相邻整数之间移动。若它访问了空缺两侧的值，就必然访问 $v$；这与 $c_v=0$ 矛盾。$\square$

引理 2

固定终点 $s$ 后，递推式唯一确定每一层已有的路径段数量 $d_v$。

证明。 从最高访问值向下看，最高层的每次访问都必须通过相邻层进入或离开，只有起点 $0$ 和终点 $s$ 会使进入数与离开数相差一。最高层给出初值；在相邻层之间应用同一流量守恒关系，即得到递推式。$\square$

引理 3

固定终点 $s$ 时，第 $v$ 层的补充方案数为 $\binom{c_v-1}{c_v-d_v}$。

证明。 已有的 $d_v$ 个路径段给出 $d_v$ 个有序插入位置。还需加入 $c_v-d_v$ 个互不区分的往返段；允许一个位置插入多个，故由插板法得到 $\binom{d_v+c_v-d_v-1}{c_v-d_v}=\binom{c_v-1}{c_v-d_v}$。$\square$

定理

算法输出所有可行隐藏数组的数量。

证明。 对每个终点 $s$，引理 2 唯一确定层间骨架；若边界不闭合则贡献为零。否则由引理 3，各层独立插入往返段，乘积恰好计数所有以 $s$ 结束的路径。不同终点的路径互不相交，求和后得到全部隐藏数组。$\square$

复杂度

完整算法对每个测试用例的时间复杂度为 $O(n^2)$，空间复杂度为 $O(n)$；阶乘预处理为 $O(\sum n)$。