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
class Solution {
 public:
  int distinctSequences(int n) {
    // dp[n][prev][prevPrev] := # of distinct sequences for n dices with
    // `prev` and `prevPrev`
    dp.resize(n + 1, vector<vector<int>>(7, vector<int>(7)));
    return distinctSequences(n, 0, 0);
  }

 private:
  constexpr static int kMod = 1'000'000'007;
  vector<vector<vector<int>>> dp;

  int distinctSequences(int n, int prev, int prevPrev) {
    if (n == 0)
      return 1;
    if (dp[n][prev][prevPrev])
      return dp[n][prev][prevPrev];

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

    return dp[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
30
class Solution {
  public int distinctSequences(int n) {
    // dp[n][prev][prevPrev] := # of distinct sequences for n dices with
    // `prev` and `prevPrev`
    dp = new int[n + 1][7][7];
    return distinctSequences(n, 0, 0);
  }

  private static final int kMod = 1_000_000_007;
  private int[][][] dp;

  private int distinctSequences(int n, int prev, int prevPrev) {
    if (n == 0)
      return 1;
    if (dp[n][prev][prevPrev] > 0)
      return dp[n][prev][prevPrev];

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

    return dp[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
class Solution:
  def distinctSequences(self, n: int) -> int:
    kMod = 1_000_000_007

    # Dp(n, prev, prevPrev ):= # Of distinct sequences for n dices with
    # `prev` and `prevPrev`
    @functools.lru_cache(None)
    def dp(n: int, prev: int, prevPrev: int) -> int:
      if n == 0:
        return 1

      ans = 0
      for dice in range(1, 7):
        if dice != prev and dice != prevPrev and \
                (prev == 0 or math.gcd(dice, prev) == 1):
          ans += dp(n - 1, dice, prev)
          ans %= kMod
      return ans

    return dp(n, 0, 0)