LeetCode 2318. Number of Distinct Roll Sequences

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
const int N = 1e4 + 1, MOD = 1e9 + 7;
int f[N][7][7];
bool valid[7][7];
class Solution {
public:
    int distinctSequences(int n) {
        fill(valid[0], valid[6] + 7, 1);
        valid[2][4] = valid[2][6] = valid[3][6] = valid[4][2] = valid[4][6] = valid[6][2] = valid[6][3] = valid[6][4] = false;
        function<int(int, int, int)> dfs = [&](int n, int p1, int p2) {
            if (n == 0) return 1;
            if (f[n][p1][p2]) return f[n][p1][p2];
            int res = 0;
            for (int x = 1; x <= 6; ++x)
                if (x != p1 && x != p2 && valid[p2][x])
                    res = (res + dfs(n - 1, p2, x)) % MOD;
            f[n][p1][p2] = res;
            return res;
        };
        return dfs(n, 0, 0);
    }
};
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
// Reference: https://leetcode.cn/problems/number-of-distinct-roll-sequences/solution/by-endlesscheng-tgkn/
const int MOD = 1e9 + 7, MX = 1e4;
int f[MX + 1][6][6];
int init = []() {
    for (int i = 0; i < 6; ++i)
        for (int j = 0; j < 6; ++j)
            if (j != i && gcd(j + 1, i + 1) == 1)
                f[2][i][j] = 1;
    for (int i = 2; i < MX; ++i)
        for (int j = 0; j < 6; ++j)
            for (int last = 0; last < 6; ++last)
                if (last != j && gcd(last + 1, j + 1) == 1)
                    for (int last2 = 0; last2 < 6; ++last2)
                        if (last2 != j && last2 != last)
                            f[i + 1][j][last] = (f[i + 1][j][last] + f[i][last][last2]) % MOD;
    return 0;
}();

class Solution {
public:
    int distinctSequences(int n) {
        if (n == 1) return 6;
        int ans = 0;
        for (int i = 0; i < 6; ++i)
            for (int j = 0; j < 6; ++j)
                ans = (ans + f[n][i][j]) % MOD;
        return ans;
    }
};
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
// Reference: https://leetcode.cn/problems/number-of-distinct-roll-sequences/solution/by-endlesscheng-tgkn/
const int MOD = 1e9 + 7, MX = 1e4;
int f[MX + 1][6];
int init = []() {
    for (int i = 0; i < 6; ++i)
        f[1][i] = 1;
    for (int i = 2; i <= MX; ++i)
        for (int j = 0; j < 6; ++j) {
            long s = 0L;
            for (int k = 0; k < 6; ++k)
                if (k != j && gcd(k + 1, j + 1) == 1)
                    s += f[i - 1][k] - f[i - 2][j];
            if (i > 3) s += f[i - 2][j];
            f[i][j] = s % MOD;
        }
    return 0;
}();

class Solution {
public:
    int distinctSequences(int n) {
        long ans = 0L;
        for (int v : f[n])
            ans += v;
        return (ans % MOD + MOD) % MOD;
    }
};