题解

思路

按数值从小到大处理操作，因为较小的数合并后可能产生较大的数，反向则不会影响已经处理过的层。

做法

设 $dp[j]$ 表示处理完所有小于 $x$ 的数后，当前有 $j$ 个 $x$ 的方案数；若输入中本来有 $b_x$ 个 $x$，选择合并 $k$ 次后会留下 $j+b_x-2k$ 个 $x$，并向下一层传递 $k$ 个 $x+1$，因此对每个 $j$ 都向 $k=0,1,\ldots,\lfloor(j+b_x)/2\rfloor$ 转移。

用差分前缀和完成这一段区间转移。第 $x$ 层可能出现的最大个数不超过 $\sum_{i\le x}b_i2^i/2^x$，把各层上界相加至多为 $2N$，再计入空层后所有状态数组总长度为 $O(N+\max A)$；处理到 $\max A+O(\log N)$ 即可得到答案。

复杂度

时间和空间复杂度均为 $O(N+\max A)$。