Skip to content

2318. Number of Distinct Roll Sequences 👍

  • Time: $O(n)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
 public:
  int distinctSequences(int n) {
    vector<vector<vector<int>>> mem(n + 1,
                                    vector<vector<int>>(7, vector<int>(7)));
    return distinctSequences(n, 0, 0, mem);
  }

 private:
  static constexpr int kMod = 1'000'000'007;

  // Returns the number of distinct sequences for n dices with `prev` and
  // `prevPrev`.
  int distinctSequences(int n, int prev, int prevPrev,
                        vector<vector<vector<int>>>& mem) {
    if (n == 0)
      return 1;
    if (mem[n][prev][prevPrev] > 0)
      return mem[n][prev][prevPrev];

    for (int dice = 1; dice <= 6; ++dice)
      if (dice != prev && dice != prevPrev &&
          (prev == 0 || gcd(dice, prev) == 1)) {
        mem[n][prev][prevPrev] += distinctSequences(n - 1, dice, prev, mem);
        mem[n][prev][prevPrev] %= kMod;
      }

    return mem[n][prev][prevPrev];
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
  public int distinctSequences(int n) {
    int[][][] mem = new int[n + 1][7][7];
    return distinctSequences(n, 0, 0);
  }

  private static final int kMod = 1_000_000_007;

  // Returns the number of distinct sequences for n dices with `prev` and
  // `prevPrev`.
  private int distinctSequences(int n, int prev, int prevPrev, int[][][] mem) {
    if (n == 0)
      return 1;
    if (mem[n][prev][prevPrev] > 0)
      return mem[n][prev][prevPrev];

    for (int dice = 1; dice <= 6; ++dice)
      if (dice != prev && dice != prevPrev && (prev == 0 || gcd(dice, prev) == 1)) {
        mem[n][prev][prevPrev] += distinctSequences(n - 1, dice, prev, mem);
        mem[n][prev][prevPrev] %= kMod;
      }

    return mem[n][prev][prevPrev];
  }

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
  def distinctSequences(self, n: int) -> int:
    kMod = 1_000_000_007

    @functools.lru_cache(None)
    def dp(n: int, prev: int, prevPrev: int) -> int:
      """
      Returns the number of distinct sequences for n dices with `prev` and
      `prevPrev`.
      """
      if n == 0:
        return 1
      res = 0
      for dice in range(1, 7):
        if (dice not in (prev, prevPrev) and
                (prev == 0 or math.gcd(dice, prev) == 1)):
          res += dp(n - 1, dice, prev)
          res %= kMod
      return res

    return dp(n, 0, 0)