不同骰子序列的数目

难度: Hard

给你一个整数 n 。你需要掷一个 6 面的骰子 n 次。请你在满足以下要求的前提下，求出不同骰子序列的数目：

序列中任意相邻数字的 最大公约数 为 1 。
序列中相等的值之间，至少有 2 个其他值的数字。正式地，如果第 i 次掷骰子的值等于第 j 次的值，那么 abs(i - j) > 2 。

请你返回不同序列的 总数目 。由于答案可能很大，请你将答案对 10⁹ + 7 取余后返回。

如果两个序列中至少有一个元素不同，那么它们被视为不同的序列。

示例 1：

输入：n = 4
输出：184
解释：一些可行的序列为 (1, 2, 3, 4) ，(6, 1, 2, 3) ，(1, 2, 3, 1) 等等。
一些不可行的序列为 (1, 2, 1, 3) ，(1, 2, 3, 6) 。
(1, 2, 1, 3) 是不可行的，因为第一个和第三个骰子值相等且 abs(1 - 3) = 2 （下标从 1 开始表示）。
(1, 2, 3, 6) i是不可行的，因为 3 和 6 的最大公约数是 3 。
总共有 184 个不同的可行序列，所以我们返回 184 。

示例 2：

输入：n = 2
输出：22
解释：一些可行的序列为 (1, 2) ，(2, 1) ，(3, 2) 。
一些不可行的序列为 (3, 6) ，(2, 4) ，因为最大公约数不为 1 。
总共有 22 个不同的可行序列，所以我们返回 22 。

提示：

1 <= n <= 10⁴

Submission

运行时间: 99 ms

内存: 18.6 MB

MOD, MX = 10 ** 9 + 7, 10 ** 4 + 1
f = [[0] * 6 for _ in range(MX + 1)]
f[1] = [1] * 6
for i in range(2, MX):
    for j in range(6):
        f[i][j] = (sum(f[i - 1][k] for k in range(6) if k != j and gcd(k + 1, j + 1) == 1)
                   - (f[2][j] - (i > 3)) * f[i - 2][j]) % MOD

class Solution:
    def distinctSequences(self, n: int) -> int:
        return sum(f[n]) % MOD

Explain

这个问题可以通过动态规划来解决。定义一个动态规划数组 f[i][j]，其中 i 表示掷骰子的次数，j 表示最后一次掷的骰子结果为 j+1（因为j是从0开始的索引）。f[i][j] 的值是所有有效序列的数量，这些序列的最后一个数字是 j+1。初始化第一次掷骰子的结果时，每个结果都只有一种可能，所以 f[1][j] = 1。对于后续的每次掷骰，需要计算基于前一次结果的有效序列数量，同时考虑两个限制条件：1) 序列中任意相邻数字的最大公约数为 1；2) 序列中相等的值之间至少有2个其他值。为了实现这一点，我们对于每个可能的 j，将所有可能的 k（不等于 j 且 gcd(k+1, j+1) == 1）的 f[i-1][k] 加总，然后从中减去不符合第二个条件的序列数量。最后，将结果模 109 + 7。

时间复杂度: O(n)

空间复杂度: O(n)

MOD, MX = 10 ** 9 + 7, 10 ** 4 + 1
# 初始化骰子结果数组，有 MX+1 行，每行6列
f = [[0] * 6 for _ in range(MX + 1)]
# 第一次掷骰子，每个结果只有一种可能
f[1] = [1] * 6
# 动态规划填表，从第二次掷骰开始计算
for i in range(2, MX):
    for j in range(6):
        # 计算当前骰子结果j+1的序列数量，不与前一个结果相同且gcd为1
        f[i][j] = (sum(f[i - 1][k] for k in range(6) if k != j and gcd(k + 1, j + 1) == 1)
                   - (f[2][j] - (i > 3)) * f[i - 2][j]) % MOD

class Solution:
    def distinctSequences(self, n: int) -> int:
        # 返回长度为n的所有有效序列的总数，结果取模
        return sum(f[n]) % MOD

Explore

在动态规划中，使用 j 来表示最后一次掷的骰子结果为 j+1 主要是为了简化数组索引的处理。由于数组索引通常从 0 开始，而骰子的结果范围是 1 到 6，直接使用 j+1 可以方便地将骰子的实际结果映射到从 0 开始的索引上。这种做法既可以避免在数组操作时进行额外的加减运算，也可以使代码更加直观易懂。

在动态规划的转移方程中，确保减去的不符合条件的序列数量正确是通过精确计算特定条件下的序列数来实现的。在题解中，我们需要减去的是那些不满足第二个条件的序列，即相等的值之间至少有2个其他值的限制。这通过从总和中减去特定的 f[i-2][j] 来实现，这代表了在当前位置使用相同值且之间只隔了一个其他值的所有序列。通过这种方式，我们能精确控制并减去那些不满足条件的序列，从而保证最终的序列数符合题目要求。

在计算 f[i][j] 时，只减去 f[i-2][j] 是基于题目条件的精确解释。题目要求相等的值之间至少有2个其他值的间隔，这意味着如果当前是第 i 次掷骰子并且结果与第 i-3 次的结果相同，则中间至少间隔了 i-2 和 i-1 两次结果，满足条件。因此，我们需要减去的只是这种最近的不满足条件的情况，即 i-2 次结果也是相同的情况，这就是为什么只考虑 f[i-2][j]。更长的间隔自然满足条件，不需要额外处理。

在代码中实现最大公约数（gcd）的条件通常可以利用许多编程语言内置的 gcd 函数。例如，在 Python 中，可以直接使用 math 模块的 gcd 函数，如 `from math import gcd`。这个函数可以高效地计算两个整数的最大公约数。如果在某些环境或语言中没有现成的 gcd 函数，也可以使用较为简单的欧几里得算法手动实现。