README_CN.md

2318. 不同骰子序列的数目

给你一个整数 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

题解 (Rust)

1. 题解

impl Solution {
    const BANS: [[usize; 4]; 6] = [
        [0, 0, 0, 0],
        [1, 3, 5, 5],
        [2, 5, 5, 5],
        [1, 3, 5, 5],
        [4, 4, 4, 4],
        [1, 2, 3, 5],
    ];
    const MOD: i32 = 1_000_000_007;

    pub fn distinct_sequences(n: i32) -> i32 {
        if n == 1 {
            return 6;
        }

        let mut dp = [[0; 6]; 6];
        let mut ret = 0;

        for i in 0..6 {
            for j in 0..6 {
                dp[i][j] = !Self::BANS[j].contains(&i) as i32;
            }
        }

        for _ in 2..n {
            let mut tmp = [[0; 6]; 6];

            for i in 0..6 {
                for j in 0..6 {
                    for k in (0..6).filter(|&x| x != i && !Self::BANS[x].contains(&j)) {
                        tmp[j][k] = (tmp[j][k] + dp[i][j]) % Self::MOD;
                    }
                }
            }

            dp = tmp;
        }

        for i in 0..6 {
            for j in 0..6 {
                ret = (ret + dp[i][j]) % Self::MOD;
            }
        }

        ret
    }
}