垒骰子

赌圣atm晚年迷恋上了垒骰子，就是把骰子一个垒在另一个上边，不能歪歪扭扭，要垒成方柱体。

经过长期观察，atm 发现了稳定骰子的奥秘：有些数字的面贴着会互相排斥！

我们先来规范一下骰子：$1$ 的对面是 $4$，$2$ 的对面是 $5$，$3$ 的对面是 $6$。

假设有 $m$ 组互斥现象，每组中的那两个数字的面紧贴在一起，骰子就不能稳定的垒起来。

atm想计算一下有多少种不同的可能的垒骰子方式。

两种垒骰子方式相同，当且仅当这两种方式中对应高度的骰子的对应数字的朝向都相同。

由于方案数可能过多，请输出模 ${10}^{9}+7$ 的结果。

输入格式

第一行包含两个整数 $n,m$，分别表示骰子的数目和排斥的组数。

接下来 $m$ 行，每行两个整数 $a,b$，表示 $a$ 和 $b$ 数字不能紧贴在一起。

输出格式

共一个数，表示答案模 ${10}^{9}+7$ 的结果。

数据范围

$1 \leq n \leq {10}^{9}$,
$1 \leq m \leq 36$,
$1 \leq a,b \leq 6$

输入样例：

2 1
1 2

输出样例：

解题思路

　　如果$n$的数据范围很小的话，可以用动态规划来做。

　　当然，因为会有一些限制，比如有$1$和$2$不可以贴在一起，那么有些集合就会变成空集。例如有$f \left( {i, 5} \right)$，那么对应的$f \left( {i-1, 1} \right)$就是空集；有$f \left( {i, 4} \right)$，那么对应的$f \left( {i-1, 2} \right)$就是空集（$1$和$2$的对立面分别是$4$和$5$）。

　　因此我们可以简化成$f\left( {i,j} \right) = {\sum\limits_{k = 1}^{6}{c_{k} \cdot f\left( {i - 1,k} \right)}}$，其中$c_{k}$等于$0$或$4$，如果有限制条件约数那么就等于$0$，否则等于$4$。

　　这种做法的时间复杂度是$O \left( n \right)$，由于$n$取到${10}^{9}$，因此会超时。

　　我们可以发现对于$f\left( {i - 1,j} \right)$，有$f\left( {i - 1,j} \right) = {\sum\limits_{k = 1}^{6}{c_{k} \cdot f\left( {i - 2,k} \right)}}$，其中每一个系数即$c_{k}$都与$f\left( {i,j} \right)$的相同，因为对于同一个$j$，他们的在每一层的限制都是一样的。因此可以抽象成矩阵相乘的形式。

　　设有向量

$$F \left( i-1 \right) = \begin{bmatrix}
f \left( {i-2, 1} \right) &
f \left( {i-2, 2} \right) &
f \left( {i-2, 3} \right) &
f \left( {i-2, 4} \right) &
f \left( {i-2, 5} \right) &
f \left( {i-2, 6} \right)
\end{bmatrix}$$

设有矩阵

$$A = \begin{bmatrix}
c_{11} & c_{12} & c_{13} & c_{14} & c_{15} & c_{16} \\
c_{21} & c_{22} & c_{23} & c_{24} & c_{25} & c_{26} \\
c_{31} & c_{32} & c_{33} & c_{34} & c_{35} & c_{36} \\
c_{41} & c_{42} & c_{43} & c_{44} & c_{45} & c_{46} \\
c_{51} & c_{52} & c_{53} & c_{54} & c_{55} & c_{56} \\
c_{61} & c_{62} & c_{63} & c_{64} & c_{65} & c_{66} \\
\end{bmatrix}$$

其中$c_{ij}$根据是否有限制取$0$或$4$。

　　可以发现有$F \left( i \right) = F \left( {i-1} \right) \times A$。递推，有$F \left( n \right) = F \left( 1 \right) \times A^{n-1}$。矩阵相乘有结合律，因此$A^{n-1}$可以用快速幂来求。

　　如何确定矩阵$A$的值？假设有限制$1$和$2$不可以贴在一起，那么如果第$n-1$个骰子最上面的数字是$1$，那么在它上面的第$n$个骰子的最上面的数字不可以是$5$（$1$和$2$不可以贴一起，而$2$的对立面是$5$），而$f \left( {i,5} \right)$是通过向量$F \left( i-1 \right)$与矩阵$A$的第$5$列相乘得到的，因此矩阵中的$c_{15}$就为$0$。同理可得$c_{24} = 0$。更一般的形式，如果有限制$x$和$y$，那么就有$c_{x \hat{y}} = c_{y \hat{x}} = 0$，其中$\hat{x}$表示$x$的对立面。

　　因为我们实现的函数是矩阵乘矩阵，因此为了统一方便，我们把向量$F \left( i \right)$也扩充乘一个$6 \times 6$矩阵，除了第一行外，其余都为$0$。

$$F \left( i \right) = \begin{bmatrix}
f \left( {i,1} \right) & f \left( {i,2} \right) & f \left( {i,3} \right) & f \left( {i,4} \right) & f \left( {i,5} \right) & f \left( {i,6} \right) \\
0 & 0 & 0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 & 0 & 0 \\
\end{bmatrix}$$

　　AC代码如下，时间复杂度为$O \left( log~n \right)$：

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 using namespace std;
 5 
 6 typedef long long LL;
 7 
 8 const int N = 6, mod = 1e9 + 7;
 9 
10 int mp[N] = {3, 4, 5, 0, 1, 2}; // 各个面的对立面映射
11 
12 void mult(int c[][N], int a[][N], int b[][N]) { // C = A * B
13     int tmp[N][N] = {0};
14     for (int i = 0; i < N; i++) {
15         for (int j = 0; j < N; j++) {
16             for (int k = 0; k < N; k++) {
17                 tmp[i][j] = (tmp[i][j] + (LL)a[i][k] * b[k][j]) % mod;
18             }
19         }
20     }
21     
22     memcpy(c, tmp, sizeof(tmp));
23 }
24 
25 int main() {
26     int n, m;
27     scanf("%d %d", &n, &m);
28     
29     int a[N][N];
30     for (int i = 0; i < N; i++) {
31         for (int j = 0; j < N; j++) {
32             a[i][j] = 4;    // 一开始先把矩阵的值都初始化为4
33         }
34     }
35     
36     while (m--) {
37         int x, y;
38         scanf("%d %d", &x, &y);
39         x--, y--;   // 为了方便，把1~6映射到0~5
40         a[x][mp[y]] = a[y][mp[x]] = 0;  // 有限制的数字取0
41     }
42     
43     // F(1)一开始为一个全4的行向量（只有一个骰子，没有限制，每个数字都有4个方向），同时把向量扩展为矩阵
44     int f[N][N] = {4, 4, 4, 4, 4, 4};
45     for (int i = n - 1; i; i >>= 1) {   // 快速幂
46         if (i & 1) mult(f, f, a);   // F = F * A
47         mult(a, a, a);  // A = A * A
48     }
49     
50     int ret = 0;
51     for (int i = 0; i < N; i++) {
52         ret = (ret + f[0][i]) % mod;
53     }
54     printf("%d", ret);
55     
56     return 0;
57 }

参考资料

　　AcWing 1217. 垒骰子（蓝桥杯C++ AB组辅导课）：https://www.acwing.com/video/793/

垒骰子

垒骰子