- $3 \le n \le 10^5$ - $2 \le k \le 10^5$ - $1 \le x \le k$ - **数据范围与子任务**：对于 $20\%$ 的数据，$n \le 10^3$ 且 $k \le 10^2$。 **示例：** 对于 $n = 4, k = 3, x = 2$，共有 **3** 种合法的数组构建方案，如图所示： - `[1, 2, 1, 2]` - `[1, 2, 3, 2]` - `[1, 3, 1, 2]` **解题思路与数学推导** 由于每个位置的元素只分为“等于 $1$”和“不等于 $1$”两种情况（因为首位确定为 $1$），我们可以使用动态规划（DP）来维护状态： 设 $dp[i]$ 表示长度为 $i+1$ 且**最后一个元素是 $1$** 的合法前缀方案数。 设 $other[i]$ 表示长度为 $i+1$ 且**最后一个元素是某个特定的非 $1$ 值（比如 $y \ne 1$）**的合法前缀方案数。 **状态转移方程：** 1. 如果第 $i$ 步以 $1$ 结尾，那么前一步 $i-1$ 必须是非 $1$ 的值。剩下的非 $1$ 的值共有 $k-1$ 种选择，所以： $$dp[i] = (k-1) \times other[i-1] \pmod{10^9 + 7}$$ 2. 如果第 $i$ 步以某个特定的非 $1$ 值 $y$ 结尾，那么前一步 $i-1$ 可以是： - 元素 $1$（贡献为 $dp[i-1]$） - 其他不为 $1$ 且不为 $y$ 的特定值。这样的值有 $k-2$ 个，每个贡献为 $other[i-1]$。 $$other[i] = (dp[i-1] + (k-2) \times other[i-1]) \pmod{10^9 + 7}$$ **初始条件**（长度为 1，即第 0 步）： - $dp[0] = 1$（首位必须是 $1$） - $other[0] = 0$（首位不能是其他值） 最终如果末位要求 $x = 1$，答案为 $dp[n-1]$；若 $x \ne 1$，答案为 $other[n-1]$。