class Solution {
public:
int distinctSequences(int n) {
}
};
2318. 不同骰子序列的数目
给你一个整数 n 。你需要掷一个 6 面的骰子 n 次。请你在满足以下要求的前提下，求出 不同 骰子序列的数目：
1 。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原站题解
python3 解法, 执行用时: 120 ms, 内存消耗: 18.9 MB, 提交时间: 2023-10-10 23:13:40
MOD, MX = 10 ** 9 + 7, 10 ** 4 + 1
f = [[0] * 6 for _ in range(MX + 1)]
f[1] = [1] * 6
for i in range(2, MX):
for j in range(6):
f[i][j] = (sum(f[i - 1][k] for k in range(6) if k != j and gcd(k + 1, j + 1) == 1)
- (f[2][j] - (i > 3)) * f[i - 2][j]) % MOD
class Solution:
def distinctSequences(self, n: int) -> int:
return sum(f[n]) % MOD
python3 解法, 执行用时: 184 ms, 内存消耗: 18.8 MB, 提交时间: 2023-10-10 23:13:30
MOD, MX = 10 ** 9 + 7, 10 ** 4 + 1
f = [[0] * 6 for _ in range(MX + 1)]
f[1] = [1] * 6
for i in range(2, MX):
for j in range(6):
for k in range(6):
if k != j and gcd(k + 1, j + 1) == 1:
f[i][j] += f[i - 1][k] - f[i - 2][j]
if i > 3: f[i][j] += f[i - 2][j]
f[i][j] %= MOD
class Solution:
def distinctSequences(self, n: int) -> int:
return sum(f[n]) % MOD
java 解法, 执行用时: 19 ms, 内存消耗: 38.3 MB, 提交时间: 2023-10-10 23:13:07
class Solution {
static final int MOD = (int) 1e9 + 7, MX = (int) 1e4;
static final int[][] f = new int[MX + 1][6];
static {
for (var i = 0; i < 6; ++i)
f[1][i] = 1;
for (var i = 2; i <= MX; ++i)
for (var j = 0; j < 6; ++j) {
var s = 0L;
for (var 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] = (int) (s % MOD);
}
}
public int distinctSequences(int n) {
var ans = 0L;
for (var v : f[n])
ans += v;
return (int) (ans % MOD + MOD) % MOD; // 保证结果非负
}
static int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}
}
java 解法, 执行用时: 25 ms, 内存消耗: 38.3 MB, 提交时间: 2023-10-10 23:12:56
class Solution {
static final int MOD = (int) 1e9 + 7, MX = (int) 1e4;
static final int[][] f = new int[MX + 1][6];
static {
for (var i = 0; i < 6; ++i)
f[1][i] = 1;
for (var i = 2; i <= MX; ++i)
for (var j = 0; j < 6; ++j) {
var s = 0L;
for (var k = 0; k < 6; ++k)
if (k != j && gcd(k + 1, j + 1) == 1)
s += f[i - 1][k];
s -= (long) (i > 3 ? f[2][j] - 1 : f[2][j]) * f[i - 2][j];
f[i][j] = (int) (s % MOD);
}
}
public int distinctSequences(int n) {
var ans = 0L;
for (var v : f[n])
ans += v;
return (int) (ans % MOD + MOD) % MOD; // 保证结果非负
}
static int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}
}
cpp 解法, 执行用时: 0 ms, 内存消耗: 6.4 MB, 提交时间: 2023-10-10 23:12:44
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];
s -= (long) (f[2][j] - (i > 3)) * 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; // 保证结果非负
}
};
cpp 解法, 执行用时: 0 ms, 内存消耗: 6.3 MB, 提交时间: 2023-10-10 23:12:33
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; // 保证结果非负
}
};
golang 解法, 执行用时: 4 ms, 内存消耗: 2.2 MB, 提交时间: 2023-10-10 23:12:15
const mod int = 1e9 + 7
var f = [1e4 + 1][6]int{}
func init() {
for i := 0; i < 6; i++ {
f[1][i] = 1
}
for i := 2; i <= 1e4; i++ {
for j := 0; j < 6; j++ {
for k := 0; k < 6; k++ {
if k != j && gcd(k+1, j+1) == 1 {
f[i][j] += f[i-1][k]
}
}
c := f[2][j]
if i > 3 {
c--
}
f[i][j] = (f[i][j] - c*f[i-2][j]) % mod
}
}
}
func distinctSequences(n int) (ans int) {
for _, v := range f[n] {
ans += v
}
return (ans%mod + mod) % mod // 保证结果非负
}
func gcd(a, b int) int {
for a != 0 {
a, b = b%a, a
}
return b
}
golang 解法, 执行用时: 0 ms, 内存消耗: 2.2 MB, 提交时间: 2023-10-10 23:12:03
/**
* 定义 f[i][j] 表示序列长度为 i，最后一个元素是 j 时的序列个数。
*/
const mod int = 1e9 + 7
var f = [1e4 + 1][6]int{}
func init() {
for i := 0; i < 6; i++ {
f[1][i] = 1
}
for i := 2; i <= 1e4; i++ {
for j := 0; j < 6; j++ {
for k := 0; k < 6; k++ {
if k != j && gcd(k+1, j+1) == 1 {
f[i][j] += f[i-1][k] - f[i-2][j]
}
}
if i > 3 {
f[i][j] += f[i-2][j]
}
f[i][j] %= mod
}
}
}
func distinctSequences(n int) (ans int) {
for _, v := range f[n] {
ans += v
}
return (ans%mod + mod) % mod // 保证结果非负
}
func gcd(a, b int) int {
for a != 0 {
a, b = b%a, a
}
return b
}
golang 解法, 执行用时: 0 ms, 内存消耗: 4.5 MB, 提交时间: 2023-10-10 23:11:21
const mod int = 1e9 + 7
var f = [1e4 + 1][6][6]int{}
func init() {
for last := 0; last < 6; last++ {
for last2 := 0; last2 < 6; last2++ {
if last2 != last && gcd(last2+1, last+1) == 1 {
f[2][last][last2] = 1
}
}
}
for i := 2; i < 1e4; i++ {
for j := 0; j < 6; j++ {
for last := 0; last < 6; last++ {
if last != j && gcd(last+1, j+1) == 1 {
for last2 := 0; last2 < 6; last2++ {
if last2 != j {
f[i+1][j][last] = (f[i+1][j][last] + f[i][last][last2]) % mod
}
}
}
}
}
}
}
func distinctSequences(n int) (ans int) {
if n == 1 {
return 6
}
for _, row := range f[n] {
for _, v := range row {
ans = (ans + v) % mod
}
}
return
}
func gcd(a, b int) int {
for a != 0 {
a, b = b%a, a
}
return b
}
cpp 解法, 执行用时: 4 ms, 内存消耗: 7.5 MB, 提交时间: 2023-10-10 23:11:05
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)
f[2][i][j] = j != i && gcd(j + 1, i + 1) == 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)
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;
}
};
java 解法, 执行用时: 52 ms, 内存消耗: 43.3 MB, 提交时间: 2023-10-10 23:10:54
class Solution {
static final int MOD = (int) 1e9 + 7, MX = (int) 1e4;
static final int[][][] f = new int[MX + 1][6][6];
static {
for (var i = 0; i < 6; ++i)
for (var j = 0; j < 6; ++j)
if (j != i && gcd(j + 1, i + 1) == 1)
f[2][i][j] = 1;
for (var i = 2; i < MX; ++i)
for (var j = 0; j < 6; ++j)
for (var last = 0; last < 6; ++last)
if (last != j && gcd(last + 1, j + 1) == 1)
for (var last2 = 0; last2 < 6; ++last2)
if (last2 != j)
f[i + 1][j][last] = (f[i + 1][j][last] + f[i][last][last2]) % MOD;
}
public int distinctSequences(int n) {
if (n == 1) return 6;
var ans = 0;
for (var i = 0; i < 6; ++i)
for (var j = 0; j < 6; ++j)
ans = (ans + f[n][i][j]) % MOD;
return ans;
}
static int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}
}
python3 解法, 执行用时: 368 ms, 内存消耗: 54 MB, 提交时间: 2023-10-10 23:10:41
@cache
def f(n: int, last: int, last2: int) -> int:
if n == 0: return 1
res = 0
for j in range(1, 7):
if j != last and j != last2 and gcd(j, last) == 1:
res += f(n - 1, j, last)
return res % (10 ** 9 + 7)
class Solution:
def distinctSequences(self, n: int) -> int:
return f(n, 7, 7) # 7 与 [1,6] 内的数字都不同且互质
python3 解法, 执行用时: 356 ms, 内存消耗: 30.1 MB, 提交时间: 2023-10-10 23:10:31
'''
三维dp
定义 f[i][last][last2] 表示序列长度为 i，最后一个元素是 last，
倒数第二个元素是 last2 的序列数目。
'''
MOD, MX = 10 ** 9 + 7, 10 ** 4
f = [[[0] * 6 for _ in range(6)] for _ in range(MX + 1)]
f[2] = [[int(j != i and gcd(j + 1, i + 1) == 1) for j in range(6)] for i in range(6)]
for i in range(2, MX):
for j in range(6):
for last in range(6):
if last != j and gcd(last + 1, j + 1) == 1:
f[i + 1][j][last] = sum(f[i][last][last2] for last2 in range(6) if last2 != j) % MOD
class Solution:
def distinctSequences(self, n: int) -> int:
return sum(sum(row) for row in f[n]) % MOD if n > 1 else 6