3802. 给纸张涂色的方式数量 🔒
题目描述
给定一个整数 n 表示纸张的数量。
同时给定一个长度为 m 的整数数组 limit，其中 limit[i] 是使用颜色 i 能够涂色的最大纸张数。
你必须在下列条件下给 所有 n 张纸涂色：
- 恰好使用两种不同 颜色。
- 每种颜色必须覆盖 连续的一段 纸张。
- 用颜色
i涂的纸张数量不能超过limit[i]。
返回一个整数表示给所有纸张染色的 不同 方式数量。由于答案可能很大，返回答案对 109 + 7 取模的结果。
注意：如果 至少 有一张纸涂上了不同的颜色，就是不同的两种方式。
示例 1：
输入：n = 4, limit = [3,1,2]
输出：6
解释：
对于每个有序数对(i, j)，其中颜色 i 被用于给第一段涂色，颜色 j 被用于给第二段涂色（i != j），x 和 4 - x 的分割是有效的，当且仅当 1 <= x <= limit[i] 且 1 <= 4 - x <= limit[j]。 合法的数对以及数量是：
(0, 1): x = 3(0, 2): x = 2, 3(1, 0): x = 1(2, 0): x = 1, 2
因此，总共有 6 种有效的方式。
示例 2：
输入：n = 3, limit = [1,2]
输出：2
解释：
对于每个有序数对 (i, j)，其中颜色 i 被用于给第一段涂色，颜色 j 被用于给第二段涂色（i != j），x 和 3 - x 的分割是有效的，当且仅当 1 <= x <= limit[i] 且 1 <= 3 - x <= limit[j]。
合法的数对和数量是：
(0, 1): x = 1(1, 0): x = 2
因此，总共有 2 种合法的方式。
示例 3：
输入：n = 3, limit = [2,2]
输出：4
解释：
对于每个有序数对 (i, j)，其中颜色 i 被用于给第一段涂色，颜色 j 被用于给第二段涂色（i != j），x 和 3 - x 的分割是有效的，当且仅当 1 <= x <= limit[i] 且 1 <= 3 - x <= limit[j]。
合法的数对和数量是：
(0, 1): x = 1, 2(1, 0): x = 1, 2
因此，总共有 4 种合法的方式。
提示：
2 <= n <= 1092 <= m == limit.length <= 1051 <= limit[i] <= 109
解法
方法一
1 | |
1 | |
1 | |
1 | |