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
Problem: 2318. 不同骰子序列的数目
[TOC]
思路
首先题目中有两个条件，第一是两个相同的点数间隔至少为2，第二是两个相邻的点数\gcd=1
- 根据第一个条件，我们就能写出一个O(6^3n)的算法，大致思路如下：
令f[i]表示前i个骰子的答案，然后三重循环枚举i,i-1,i-2这三颗骰子的点数即可。 - 根据第二个条件，可以将该算法优化至O(66n)，即三颗骰子只有66种合法状态，
大力写转移方程即可
能不能再优化一下呢？可以！
解题方法
考虑一个合法的序列，如果将1/5,2/4对调，该序列还合法吗？
是合法的！
因此将相邻的点数分为9类：12/14/52/54,13/53,16/56,21/25/41/45,23/43,31/35,32/34,61/65,15/51，用f[0…8]表示。
转移方程分析如下，以(12/14/52/54)为例：
(i-1,i)点数为(12/14/52/54)，则i-1为1或5，i-2不能为2或4。
哪些可以转移到呢？
- 21/25/41/45，41\to 12/21\to 14/45\to 52/25\to 54
- 31/35，31\to 12/31\to 14/35\to 52/35\to 54
- 61/65，61\to 12/61\to 14/65\to 52/65\to 54
- 15/51，51\to 12/51\to 14/15\to 52/15\to 54
转移方程为f[i][12/14/52/54]=f[i-1][21/25/41/45]+2f[i-1][31/35]+2f[i-1][61/65]+2f[i-1][15/51]，也就是
f[i][0]=f[i-1][3]+2f[i-1][5]+2f[i-1][7]+2f[i-1][8]
使用滚动数组，即f_{new}[0]=f[3]+2f[5]+2f[7]+2f[8]
其他几类仿照上述过程分析即可，最后得出：
f_{new}[0]=f[3]+2f[5]+2f[7]+2f[8]
f_{new}[1]=f[3]+f[7]+f[8]
f_{new}[2]=f[3]+f[5]+f[8]
f_{new}[3]=f[0]+2f[6]
f_{new}[4]=f[0]
f_{new}[5]=f[1]+2f[4]
f_{new}[6]=2f[1]+f[4]
f_{new}[7]=f[2]
f_{new}[8]=f[3]+f[5]+f[7]
复杂度
时间复杂度: O(9n)
空间复杂度: 仅消耗常数级别的空间
Code
1 |
|