题目链接
题解动态规划 或 矩阵快速幂。
动态规划这个方法只能得到 78% 的分数，无法 AC，但确实比较好想。
笼统地说一下状态定义和转移方程。
dp[i][j]表示从下向上数第i个骰子的上面点数为j的情况下，靠下的i个骰子摆放的全部方案数。（这个定义不准确，后面会说）
那么转移方程可以比较容易地写出来了，第i个骰子上面点数为1，对应地其下面点数为4，因此第i个骰子上面点数为1的方案数（即dp[i][1]）为第i-1个骰子上面点数不与第i个骰子下面点数4相排斥的情况数之和，即Σ{dp[i-1][k]}，其中k为不与4排斥的点数；同理，dp[i][2]=Σ{dp[i-1][k]}，其中k为不与5（即2的对面点数）相排斥的点数；其他点数类似。
以样例为例，总共两个骰子，点数1与点数2排斥。
也就是说如果第二个骰子（从下向上数）上面点数为5，换句话说就是第二个骰子的下面点数为2，则第一个骰子上面的点数就不能为1；如果第二个骰子上面点数为4，则第二个骰子上面的点数不能为2。
因此，
dp[2][1] = dp[1][1] + dp[1][2] + dp[1][3] + dp[1][4] + dp[1][5] + dp[1][6]
dp[2][2] = dp[1][1] + dp[1][2] + dp[1][3] + dp[1][4] + dp[1][5] + dp[1][6]
dp[2][3] = dp[1][1] + dp[1][2] + dp[1][3] + dp[1][4] + dp[1][5] + dp[1][6]
dp[2][4] = dp[1][1] + dp[1][3] + dp[1][4] + dp[1][5] + dp[1][6]
dp[2][5] = dp[1][2] + dp[1][3] + dp[1][4] + dp[1][5] + dp[1][6]
dp[2][6] = dp[1][1] + dp[1][2] + dp[1][3] + dp[1][4] + dp[1][5] + dp[1][6]
应该注意到“两种垒骰子方式相同，当且仅当这两种方式中对应高度的骰子的对应数字的朝向都相同”，也就是说，如果保证了某个骰子上面点数为1，也就保证了其下面点数为4，但是可以水平旋转0°、90°、180°或270°，也就是前后面和左右面的点数可以变化，这样也算不同的方案。
我们上面的对状态的定义很显然只保证了上下两面确定，也就是说我们错误地理解成了“两种垒骰子方式相同，当且仅当这两种方式中对应高度的骰子的上下两面的点数相同”。由于我们保证了上下两面不会出现排斥，所以只需要在此基础上水平方向上旋转骰子即可，每一个骰子确定的一种上下面都对应着四种情况（这句话的理解就是，如果某个骰子上下面的取值可能为：{1, 4} 、{3, 6} 和 {4, 1} ，那么按我们最初的理解只有该骰子只有三种摆放方式，但其实该骰子水平旋转是不影响上下面的，也就是不影响上下骰子的排斥关系的，所以我们可以尽情地旋转。{1, 4} 时，我们有四种旋转方法，{3, 6} 时，我们有四种旋转方法，{4, 1} 时，我们有四种旋转方法，因此总共12种方法，即3×4）。
这样一来，前i层骰子总共具有(4^i)*(dp[i][1]+...+dp[i][6])种摆法。
我们完全可以先按照最初对dp的定义方式和转移方式去计算，最后再乘以4^n即可。
矩阵快速幂基础讲解
首先根据上面对动态规划方法的理解，我们可以发现递推的转移方程：dp[i][j] = dp[i-1][k]，k为与abs(3-j)不排斥的点数。
我们定义几个矩阵：
(
d
p
[
i
−
1
]
[
1
]
d
p
[
i
−
1
]
[
2
]
d
p
[
i
−
1
]
[
3
]
d
p
[
i
−
1
]
[
4
]
d
p
[
i
−
1
]
[
5
]
d
p
[
i
−
1
]
[
6
]
)
\left( \begin{matrix} dp[i-1][1] \\ dp[i-1][2] \\ dp[i-1][3] \\ dp[i-1][4] \\ dp[i-1][5] \\ dp[i-1][6] \\ \end{matrix} \right)
⎝⎜⎜⎜⎜⎜⎜⎛dp[i−1][1]dp[i−1][2]dp[i−1][3]dp[i−1][4]dp[i−1][5]dp[i−1][6]⎠⎟⎟⎟⎟⎟⎟⎞ 为了方便，我们给这个矩阵起名叫i-1层矩阵
X
i
−
1
X_{i-1}
Xi−1。
( d p [ i ] [ 1 ] d p [ i ] [ 2 ] d p [ i ] [ 3 ] d p [ i ] [ 4 ] d p [ i ] [ 5 ] d p [ i ] [ 6 ] ) \left( \begin{matrix} dp[i][1] \\ dp[i][2] \\ dp[i][3] \\ dp[i][4] \\ dp[i][5] \\ dp[i][6] \\ \end{matrix} \right) ⎝⎜⎜⎜⎜⎜⎜⎛dp[i][1]dp[i][2]dp[i][3]dp[i][4]dp[i][5]dp[i][6]⎠⎟⎟⎟⎟⎟⎟⎞
同理，这个就叫i层矩阵
X
i
X_i
Xi。
这俩矩阵具有什么关系呢？
由转移方程可知，第i层矩阵的每个元素都可以表示成第i-1层矩阵中的某些元素之和，而这些所谓的“某些”，正是第二维度为k的那些元素。
还是以样例为例。
第1层矩阵为：
(
1
1
1
1
1
1
)
\left(\begin{matrix}1 \\1 \\1 \\1 \\1 \\1 \\\end{matrix}\right)
⎝⎜⎜⎜⎜⎜⎜⎛111111⎠⎟⎟⎟⎟⎟⎟⎞，为了得到第2层矩阵，我们需要让第1层矩阵左乘一个
6
×
6
6×6
6×6的矩阵得到
6
×
1
6×1
6×1的第2层矩阵（线性代数基础）。
假设 6 × 6 6×6 6×6的矩阵为 ( a 11 a 12 . . . a 16 a 21 a 22 . . . a 26 . . . . . . . . . a 61 a 62 . . . a 66 ) 6 × 6 \left(\begin{matrix}a_{11} & a_{12} & ... & a_{16} \\ a_{21} & a_{22} & ... & a_{26} \\ ...& ... &&... \\a_{61} & a_{62} & ... & a_{66}\\\end{matrix}\right)_{6×6} ⎝⎜⎜⎛a11a21...a61a12a22...a62.........a16a26...a66⎠⎟⎟⎞6×6，称为系数矩阵 A A A。
这个系数矩阵显然是由1和0构成的，即选或者不选。而且这个矩阵满足
A
∗
X
i
−
1
=
X
i
A*X_{i-1}=X_i
A∗Xi−1=Xi。
根据上述矩阵的定义和转移方程的含义，我们可以推算出系数矩阵的哪些位置为1，哪些位置为0。更直接点，上面不是写了一串dp[2][i] = ……了嘛，直接将这个方程组转换为矩阵乘法（线性代数基础）。
可以得到：
( d p [ 2 ] [ 1 ] d p [ 2 ] [ 2 ] d p [ 2 ] [ 3 ] d p [ 2 ] [ 4 ] d p [ 2 ] [ 5 ] d p [ 2 ] [ 6 ] ) = ( 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 ) ( d p [ 1 ] [ 1 ] d p [ 1 ] [ 2 ] d p [ 1 ] [ 3 ] d p [ 1 ] [ 4 ] d p [ 1 ] [ 5 ] d p [ 1 ] [ 6 ] ) \left( \begin{matrix} dp[2][1] \\ dp[2][2] \\ dp[2][3] \\ dp[2][4] \\ dp[2][5] \\ dp[2][6] \\ \end{matrix} \right) = \left( \begin{matrix} 1 & 1 & 1 & 1 & 1& 1 \\ 1 & 1 & 1 & 1 & 1& 1 \\ 1 & 1 & 1 & 1 & 1& 1 \\ 1 & 0 & 1 & 1 & 1& 1 \\ 0 & 1 & 1 & 1 & 1& 1 \\ 1 & 1 & 1 & 1 & 1& 1 \\ \end{matrix} \right) \left( \begin{matrix} dp[1][1] \\ dp[1][2] \\ dp[1][3] \\ dp[1][4] \\ dp[1][5] \\ dp[1][6] \\ \end{matrix} \right) ⎝⎜⎜⎜⎜⎜⎜⎛dp[2][1]dp[2][2]dp[2][3]dp[2][4]dp[2][5]dp[2][6]⎠⎟⎟⎟⎟⎟⎟⎞=⎝⎜⎜⎜⎜⎜⎜⎛111101111011111111111111111111111111⎠⎟⎟⎟⎟⎟⎟⎞⎝⎜⎜⎜⎜⎜⎜⎛dp[1][1]dp[1][2]dp[1][3]dp[1][4]dp[1][5]dp[1][6]⎠⎟⎟⎟⎟⎟⎟⎞
把数值代入得到：
( 6 6 6 5 5 6 ) = ( 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 ) ( 1 1 1 1 1 1 ) \left( \begin{matrix} 6 \\ 6\\ 6\\ 5 \\ 5\\ 6 \\ \end{matrix} \right) = \left( \begin{matrix} 1 & 1 & 1 & 1 & 1& 1 \\ 1 & 1 & 1 & 1 & 1& 1 \\ 1 & 1 & 1 & 1 & 1& 1 \\ 1 & 0 & 1 & 1 & 1& 1 \\ 0 & 1 & 1 & 1 & 1& 1 \\ 1 & 1 & 1 & 1 & 1& 1 \\ \end{matrix} \right) \left( \begin{matrix} 1\\ 1 \\ 1 \\ 1\\ 1 \\ 1\\ \end{matrix} \right) ⎝⎜⎜⎜⎜⎜⎜⎛666556⎠⎟⎟⎟⎟⎟⎟⎞=⎝⎜⎜⎜⎜⎜⎜⎛111101111011111111111111111111111111⎠⎟⎟⎟⎟⎟⎟⎞⎝⎜⎜⎜⎜⎜⎜⎛111111⎠⎟⎟⎟⎟⎟⎟⎞
递推公式为： ( d p [ i ] [ 1 ] d p [ i ] [ 2 ] d p [ i ] [ 3 ] d p [ i ] [ 4 ] d p [ i ] [ 5 ] d p [ i ] [ 6 ] ) = ( 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 ) ( d p [ i − 1 ] [ 1 ] d p [ i − 1 ] [ 2 ] d p [ i − 1 ] [ 3 ] d p [ i − 1 ] [ 4 ] d p [ i − 1 ] [ 5 ] d p [ i − 1 ] [ 6 ] ) \left( \begin{matrix} dp[i][1] \\ dp[i][2] \\ dp[i][3] \\ dp[i][4] \\ dp[i][5] \\ dp[i][6] \\ \end{matrix} \right) = \left( \begin{matrix} 1 & 1 & 1 & 1 & 1& 1 \\ 1 & 1 & 1 & 1 & 1& 1 \\ 1 & 1 & 1 & 1 & 1& 1 \\ 1 & 0 & 1 & 1 & 1& 1 \\ 0 & 1 & 1 & 1 & 1& 1 \\ 1 & 1 & 1 & 1 & 1& 1 \\ \end{matrix} \right) \left( \begin{matrix} dp[i-1][1] \\ dp[i-1][2] \\ dp[i-1][3] \\ dp[i-1][4] \\ dp[i-1][5] \\ dp[i-1][6] \\ \end{matrix} \right) ⎝⎜⎜⎜⎜⎜⎜⎛dp[i][1]dp[i][2]dp[i][3]dp[i][4]dp[i][5]dp[i][6]⎠⎟⎟⎟⎟⎟⎟⎞=⎝⎜⎜⎜⎜⎜⎜⎛111101111011111111111111111111111111⎠⎟⎟⎟⎟⎟⎟⎞⎝⎜⎜⎜⎜⎜⎜⎛dp[i−1][1]dp[i−1][2]dp[i−1][3]dp[i−1][4]dp[i−1][5]dp[i−1][6]⎠⎟⎟⎟⎟⎟⎟⎞
由 X 1 X_1 X1推出 X n X_n Xn并不是件难事： ( d p [ n ] [ 1 ] d p [ n ] [ 2 ] d p [ n ] [ 3 ] d p [ n ] [ 4 ] d p [ n ] [ 5 ] d p [ n ] [ 6 ] ) = ( 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 ) n − 1 ( d p [ 1 ] [ 1 ] d p [ 1 ] [ 2 ] d p [ 1 ] [ 3 ] d p [ 1 ] [ 4 ] d p [ 1 ] [ 5 ] d p [ 1 ] [ 6 ] ) \left( \begin{matrix} dp[n][1] \\ dp[n][2] \\ dp[n][3] \\ dp[n][4] \\ dp[n][5] \\ dp[n][6] \\ \end{matrix} \right) = \left( \begin{matrix} 1 & 1 & 1 & 1 & 1& 1 \\ 1 & 1 & 1 & 1 & 1& 1 \\ 1 & 1 & 1 & 1 & 1& 1 \\ 1 & 0 & 1 & 1 & 1& 1 \\ 0 & 1 & 1 & 1 & 1& 1 \\ 1 & 1 & 1 & 1 & 1& 1 \\ \end{matrix} \right)^{n-1} \left( \begin{matrix} dp[1][1] \\ dp[1][2] \\ dp[1][3] \\ dp[1][4] \\ dp[1][5] \\ dp[1][6] \\ \end{matrix} \right) ⎝⎜⎜⎜⎜⎜⎜⎛dp[n][1]dp[n][2]dp[n][3]dp[n][4]dp[n][5]dp[n][6]⎠⎟⎟⎟⎟⎟⎟⎞=⎝⎜⎜⎜⎜⎜⎜⎛111101111011111111111111111111111111⎠⎟⎟⎟⎟⎟⎟⎞n−1⎝⎜⎜⎜⎜⎜⎜⎛dp[1][1]dp[1][2]dp[1][3]dp[1][4]dp[1][5]dp[1][6]⎠⎟⎟⎟⎟⎟⎟⎞
由此，我们发现可以使用矩阵快速幂了。
最后的结果是什么呢？
首先将dp[n][i]求和，再乘以4^n就是结果。
发现这样有点笨，反正矩阵快速幂是进行快速幂计算，4^n也是进行快速幂计算，那将4^n的计算也放在矩阵快速幂中计算不就好了嘛。
我们将
X
1
X_1
X1改为
(
4
4
4
4
4
4
)
\left(\begin{matrix}4 \\4 \\4 \\4 \\4 \\4 \\\end{matrix}\right)
⎝⎜⎜⎜⎜⎜⎜⎛444444⎠⎟⎟⎟⎟⎟⎟⎞，再将系数矩阵
A
A
A之前填1的地方改为4，这样就实现了4^n一起算了。
( a n s [ n ] [ 1 ] a n s [ n ] [ 2 ] a n s [ n ] [ 3 ] a n s [ n ] [ 4 ] a n s [ n ] [ 5 ] a n s [ n ] [ 6 ] ) = ( 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 0 4 4 4 4 0 4 4 4 4 4 4 4 4 4 4 4 ) n − 1 ( 4 4 4 4 4 4 ) \left( \begin{matrix} ans[n][1] \\ ans[n][2] \\ ans[n][3] \\ ans[n][4] \\ ans[n][5] \\ ans[n][6] \\ \end{matrix} \right) = \left( \begin{matrix} 4 & 4 & 4 & 4 & 4& 4 \\ 4 & 4 & 4 & 4 & 4& 4 \\ 4 & 4 & 4 & 4 & 4& 4 \\ 4 & 0 & 4 & 4 & 4& 4 \\ 0 & 4 & 4 & 4 & 4& 4 \\ 4 & 4 & 4 & 4 & 4& 4 \\ \end{matrix} \right)^{n-1} \left( \begin{matrix} 4 \\ 4 \\ 4 \\ 4 \\ 4 \\ 4 \\ \end{matrix} \right) ⎝⎜⎜⎜⎜⎜⎜⎛ans[n][1]ans[n][2]ans[n][3]ans[n][4]ans[n][5]ans[n][6]⎠⎟⎟⎟⎟⎟⎟⎞=⎝⎜⎜⎜⎜⎜⎜⎛444404444044444444444444444444444444⎠⎟⎟⎟⎟⎟⎟⎞n−1⎝⎜⎜⎜⎜⎜⎜⎛444444⎠⎟⎟⎟⎟⎟⎟⎞
进一步思考。
上面的系数矩阵
A
A
A是以第n个矩阵上面点数为1~6表示算出的方案数，那如果想用下面点数表示，系数矩阵又变成了什么样？
还是根据矩阵的定义和转移方程的含义用4和0填充系数矩阵，也可以像上面那样列出每一个情况的转移方程，再将方程组转换为矩阵的表达形式。
还是以样例为例，如果是以每个骰子下面点数来计算方案数，则转移方程的矩阵表达为：
( 5 5 6 6 6 6 ) = ( 4 4 4 4 0 4 4 4 4 0 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 ) ( 4 4 4 4 4 4 ) \left( \begin{matrix} 5 \\ 5 \\ 6 \\ 6 \\ 6\\ 6 \\ \end{matrix} \right) = \left( \begin{matrix} 4 & 4 & 4 & 4 & 0& 4 \\ 4 & 4 & 4 & 0 & 4& 4 \\ 4 & 4 & 4 & 4 & 4& 4 \\ 4 & 4 & 4 & 4 & 4& 4 \\ 4 & 4 & 4 & 4 & 4& 4 \\ 4 & 4 & 4 & 4 & 4& 4 \\ \end{matrix} \right) \left( \begin{matrix} 4 \\ 4 \\ 4 \\ 4 \\ 4 \\ 4 \\ \end{matrix} \right) ⎝⎜⎜⎜⎜⎜⎜⎛556666⎠⎟⎟⎟⎟⎟⎟⎞=⎝⎜⎜⎜⎜⎜⎜⎛444444444444444444404444044444444444⎠⎟⎟⎟⎟⎟⎟⎞⎝⎜⎜⎜⎜⎜⎜⎛444444⎠⎟⎟⎟⎟⎟⎟⎞
由 X 1 X_1 X1推出 X n X_n Xn：
( a n s [ n ] [ 1 ] a n s [ n ] [ 2 ] a n s [ n ] [ 3 ] a n s [ n ] [ 4 ] a n s [ n ] [ 5 ] a n s [ n ] [ 6 ] ) = ( 4 4 4 4 0 4 4 4 4 0 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 ) n − 1 ( 4 4 4 4 4 4 ) \left( \begin{matrix} ans[n][1] \\ ans[n][2] \\ ans[n][3] \\ ans[n][4] \\ ans[n][5] \\ ans[n][6] \\ \end{matrix} \right) = \left( \begin{matrix} 4 & 4 & 4 & 4 & 0& 4 \\ 4 & 4 & 4 & 0 & 4& 4 \\ 4 & 4 & 4 & 4 & 4& 4 \\ 4 & 4 & 4 & 4 & 4& 4 \\ 4 & 4 & 4 & 4 & 4& 4 \\ 4 & 4 & 4 & 4 & 4& 4 \\ \end{matrix} \right)^{n-1} \left( \begin{matrix} 4 \\ 4 \\ 4 \\ 4 \\ 4 \\ 4 \\ \end{matrix} \right) ⎝⎜⎜⎜⎜⎜⎜⎛ans[n][1]ans[n][2]ans[n][3]ans[n][4]ans[n][5]ans[n][6]⎠⎟⎟⎟⎟⎟⎟⎞=⎝⎜⎜⎜⎜⎜⎜⎛444444444444444444404444044444444444⎠⎟⎟⎟⎟⎟⎟⎞n−1⎝⎜⎜⎜⎜⎜⎜⎛444444⎠⎟⎟⎟⎟⎟⎟⎞
总结一下，我们到底如何根据输入的排斥点对，来确定系数矩阵的哪些位置为0。
假设排斥点对为 {a, b}。
如果是以上面点数表示的方案数，则应该将矩阵的第a的反面行第b列和第b的反面行第a列设置为0，其余位置设置为4； 如果是以下面点数表示的方案数，则应该将矩阵的第a行第b的反面列和第b行第a的反面列设置为0，其余位置设置为4.
无论哪种方式最后计算的结果都一样。
（建议自己理解一下两种方式如此设置的原因，还是根据矩阵的定义和转移方程的含义理解）
再就是自己实现一下代码了，数据结构的设计比较重要（我就是因为数据结构定义的很拉跨所以debug都费劲）
我不理解为什么归为“简单”？？？？？？？？？？
代码 动态规划// 78%
#include
using namespace std;
const int MOD = 1e9+7;
typedef long long ll;
int op[7] = {0, 4, 5, 6, 1, 2, 3}; // op[1]=4, op[2]=5, op[3]=6, op[4]=1, op[5]=2, op[6]=3
int n, m, a, b;
ll dp[2][7]; // dp[i][j]表示第i个骰子的上面点数为j的情况下，底下的i个骰子的方案数
// dp采用滚动数组的方式保存
ll c = 4; // 初始设为4，因为下面循环从第二个骰子开始，c的初始值为第一个骰子的可能数。
ll ans;
bool duili[7][7];
int main()
{
memset (duili, false, sizeof duili);
cin >> n >> m;
for (int i = 1;i > a >> b;
duili[a][b] = duili[b][a] = true; // 这个表示方法没想到
}
for (int i = 1;i
关注
打赏
![]()
1662186765
查看更多评论
最近更新
- 深拷贝和浅拷贝的区别（重点）
- 【Vue】走进Vue框架世界
- 【云服务器】项目部署—搭建网站—vue电商后台管理系统
- 【React介绍】 一文带你深入React
- 【React】React组件实例的三大属性之state，props，refs（你学废了吗）
- 【脚手架VueCLI】从零开始，创建一个VUE项目
- 【React】深入理解React组件生命周期----图文详解（含代码）
- 【React】DOM的Diffing算法是什么？以及DOM中key的作用----经典面试题
- 【React】1_使用React脚手架创建项目步骤--------详解(含项目结构说明)
- 【React】2_如何使用react脚手架写一个简单的页面？
