Question

2318. 不同骰子序列的数目

English Version

题目描述

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

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

请你返回不同序列的 总数目 。由于答案可能很大，请你将答案对 109 + 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 <= 104

解法

方法一：动态规划

三维 DP。

设 $dp[k][i][j]$ 表示序列长度为 $k$，且序列的最后两个数字分别为 $i$, $j$ 的所有满足要求的不同序列的数量。

class Solution:
  def distinctSequences(self, n: int) -> int:
    if n == 1:
      return 6
    mod = 10**9 + 7
    dp = [[[0] * 6 for _ in range(6)] for _ in range(n + 1)]
    for i in range(6):
      for j in range(6):
        if gcd(i + 1, j + 1) == 1 and i != j:
          dp[2][i][j] = 1
    for k in range(3, n + 1):
      for i in range(6):
        for j in range(6):
          if gcd(i + 1, j + 1) == 1 and i != j:
            for h in range(6):
              if gcd(h + 1, i + 1) == 1 and h != i and h != j:
                dp[k][i][j] += dp[k - 1][h][i]
    ans = 0
    for i in range(6):
      for j in range(6):
        ans += dp[-1][i][j]
    return ans % mod

class Solution {
  public int distinctSequences(int n) {
    if (n == 1) {
      return 6;
    }
    int mod = (int) 1e9 + 7;
    int[][][] dp = new int[n + 1][6][6];
    for (int i = 0; i < 6; ++i) {
      for (int j = 0; j < 6; ++j) {
        if (gcd(i + 1, j + 1) == 1 && i != j) {
          dp[2][i][j] = 1;
        }
      }
    }
    for (int k = 3; k <= n; ++k) {
      for (int i = 0; i < 6; ++i) {
        for (int j = 0; j < 6; ++j) {
          if (gcd(i + 1, j + 1) == 1 && i != j) {
            for (int h = 0; h < 6; ++h) {
              if (gcd(h + 1, i + 1) == 1 && h != i && h != j) {
                dp[k][i][j] = (dp[k][i][j] + dp[k - 1][h][i]) % mod;
              }
            }
          }
        }
      }
    }
    int ans = 0;
    for (int i = 0; i < 6; ++i) {
      for (int j = 0; j < 6; ++j) {
        ans = (ans + dp[n][i][j]) % mod;
      }
    }
    return ans;
  }

  private int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
  }
}

class Solution {
public:
  int distinctSequences(int n) {
    if (n == 1) return 6;
    int mod = 1e9 + 7;
    vector<vector<vector<int>>> dp(n + 1, vector<vector<int>>(6, vector<int>(6)));
    for (int i = 0; i < 6; ++i)
      for (int j = 0; j < 6; ++j)
        if (gcd(i + 1, j + 1) == 1 && i != j)
          dp[2][i][j] = 1;
    for (int k = 3; k <= n; ++k)
      for (int i = 0; i < 6; ++i)
        for (int j = 0; j < 6; ++j)
          if (gcd(i + 1, j + 1) == 1 && i != j)
            for (int h = 0; h < 6; ++h)
              if (gcd(h + 1, i + 1) == 1 && h != i && h != j)
                dp[k][i][j] = (dp[k][i][j] + dp[k - 1][h][i]) % mod;
    int ans = 0;
    for (int i = 0; i < 6; ++i)
      for (int j = 0; j < 6; ++j)
        ans = (ans + dp[n][i][j]) % mod;
    return ans;
  }

  int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
  }
};

func distinctSequences(n int) int {
  if n == 1 {
    return 6
  }
  dp := make([][][]int, n+1)
  for k := range dp {
    dp[k] = make([][]int, 6)
    for i := range dp[k] {
      dp[k][i] = make([]int, 6)
    }
  }
  for i := 0; i < 6; i++ {
    for j := 0; j < 6; j++ {
      if gcd(i+1, j+1) == 1 && i != j {
        dp[2][i][j] = 1
      }
    }
  }
  mod := int(1e9) + 7
  for k := 3; k <= n; k++ {
    for i := 0; i < 6; i++ {
      for j := 0; j < 6; j++ {
        if gcd(i+1, j+1) == 1 && i != j {
          for h := 0; h < 6; h++ {
            if gcd(h+1, i+1) == 1 && h != i && h != j {
              dp[k][i][j] = (dp[k][i][j] + dp[k-1][h][i]) % mod
            }
          }
        }
      }
    }
  }
  ans := 0
  for i := 0; i < 6; i++ {
    for j := 0; j < 6; j++ {
      ans = (ans + dp[n][i][j]) % mod
    }
  }
  return ans
}

func gcd(a, b int) int {
  if b == 0 {
    return a
  }
  return gcd(b, a%b)
}