题解

思路

固定一组相邻差值

$$d_i=a_{i+1}-a_i\in[-k,k]\qquad(1\le i<n).$$

将这些差值对应的折线整体上下平移，可以令它的最小值恰好等于任意给定的非负整数 $b$，而所得数组唯一。因此，最小值恰好为 $b$ 的合法相邻差数组有

$$(2k+1)^{n-1}$$

个。

若数组的最小值不超过 $x+k-1$，但最大值至少为 $x$，那么沿相邻差不超过 $k$ 的序列从较小值走到较大值时，一定会经过区间 $[x,x+k-1]$。反过来，华丽数组显然满足这两个条件。

于是先统计最小值属于 $[0,x+k-1]$ 的数组，再减去所有元素均小于 $x$ 的数组：

$$\mathrm{ans}=(x+k)(2k+1)^{n-1}-B(n,x,k),$$

其中 $B(n,x,k)$ 表示所有元素都属于 $[0,x-1]$ 且相邻差不超过 $k$ 的数组数量。

做法

子任务 1：完整枚举数组

若一个华丽数组已经访问过 $[x,x+k-1]$，则任意位置的值都不会超过

$$x+k-1+(n-1)k.$$

在 $n\le5,k\le2,x\le3$ 时，可以深度优先枚举这个有限范围内的全部数组；加入新元素时直接检查它与前一项的差，再在叶子判断是否访问目标区间。

这是直接按定义求解的独立算法。其最坏搜索规模在本子任务内很小。

子任务 2：逐位置动态规划

计算 $B$。令 $dp_v$ 表示当前序列最后一个数为 $v$ 的方案数，其中 $0\le v<x$。初始时每个 $dp_v=1$。每扩展一位，有

$$dp'_v=\sum_{\substack{0\le u<x\\|u-v|\le k}}dp_u.$$

进行 $n-1$ 次转移后，$B=\sum_v dp_v$。复杂度为 $O(nx^2)$，空间复杂度为 $O(x)$。结合 $\sum n\le5000$ 和 $x\le40$ 可以通过。

子任务 3：矩阵快速幂

把上面的转移写成 $x\times x$ 矩阵 $A$：

$$A_{i,j}=[|i-j|\le k].$$

长度为 $1$ 时的状态向量为全 $1$。因此

$$B(n,x,k)=\boldsymbol 1^{\mathsf T}A^{n-1}\boldsymbol 1.$$

用二进制矩阵快速幂计算 $A^{n-1}$。当 $x=0$ 时，没有“小于 $x$ 的非负整数”，故直接令 $B=0$。

总复杂度为 $O(x^3\log n)$，空间复杂度为 $O(x^2)$。

正确性证明

引理 1

对任意固定的相邻差序列 $d_1,\ldots,d_{n-1}\in[-k,k]$ 和任意非负整数 $b$，恰有一个非负整数数组具有这些相邻差且最小值为 $b$。

证明。 令前缀和为 $s_1=0,s_i=\sum_{j<i}d_j$。取 $a_i=s_i+b-\min_j s_j$ 即可，且整体平移量由最小值必须为 $b$ 唯一确定。$\square$

引理 2

满足相邻差绝对值不超过 $k$ 的数组是华丽数组，当且仅当其最小值不超过 $x+k-1$ 且最大值至少为 $x$。

证明。 必要性直接由数组中存在 $[x,x+k-1]$ 内元素得到。充分性方面，沿数组从某个不超过 $x+k-1$ 的最小值位置走向某个至少为 $x$ 的最大值位置；若尚未到达 $x$，一步最多增加 $k$，第一次到达至少 $x$ 时的值不超过 $x+k-1$。$\square$

引理 3

$B(n,x,k)=\boldsymbol 1^{\mathsf T}A^{n-1}\boldsymbol 1$。

证明。 矩阵 $A$ 的一条边恰好表示两个相邻取值满足差值限制。全 $1$ 初始向量枚举首项，连续乘 $n-1$ 次枚举其余位置，最后求和枚举末项。每个全程位于 $[0,x-1]$ 的数组被计数恰好一次。$\square$

定理

算法输出华丽数组数量。

证明。 由引理 1，最小值属于 $[0,x+k-1]$ 的数组共有 $(x+k)(2k+1)^{n-1}$ 个。由引理 2，其中不华丽的恰是全部元素均小于 $x$ 的数组；由引理 3，其数量为 $B(n,x,k)$。两者相减即为答案。$\square$

复杂度

每个测试用例时间复杂度为 $O(x^3\log n)$，空间复杂度为 $O(x^2)$。