3916. 锯齿形数组的总数 III 🔒
题目描述
给你三个整数 n、l 和 r。
长度为 n 的锯齿形数组定义如下：
- 每个元素的取值范围为
[l, r]。 - 任意 两个 相邻的元素都不相等。
- 任意 三个 连续的元素不能构成一个 严格递增 或 严格递减 的序列。
返回满足条件的锯齿形数组的总数。
由于答案可能很大，请将结果对 109 + 7 取余数。
示例 1：
输入：n = 3, l = 4, r = 5
输出：2
解释：
在取值范围 [4, 5] 内，长度为 n = 3 的锯齿形数组只有 2 种：
[4, 5, 4][5, 4, 5]
示例 2：
输入：n = 3, l = 1, r = 3
输出：10
解释：
在取值范围 [1, 3] 内，长度为 n = 3 的锯齿形数组共有 10 种：
[1, 2, 1],[1, 3, 1],[1, 3, 2][2, 1, 2],[2, 1, 3],[2, 3, 1],[2, 3, 2][3, 1, 2],[3, 1, 3],[3, 2, 3]
所有数组均符合锯齿形条件。
提示：
3 <= n <= 2001 <= l < r <= 109
解法
方法一
思考
取值区间长度可达 \(10^9\)，而 \(n\le 200\)，不能按具体数值枚举。锯齿条件只约束相邻三项的升降关系，与绝对值无关，真正起作用的是相对大小。
将 \([l,r]\) 离散为长度 \(m=r-l+1\) 的全序后，状态可压成「前一项取值、当前升降方向」。\(m\) 仍可能很大，需要把对取值的转移写成前缀和或矩阵形式，才能在 \(O(n\cdot\mathrm{polylog}\,m)\) 或等价的值域 DP 中完成。
仓库中该题尚无实现代码，思考止于「值域过大、须对相对次序做 DP」这一观察。
1 | |
1 | |
1 | |
1 | |