1217. 垒骰子
摘要
Title: 1217. 垒骰子
Tag: dp、矩阵快速幂
Memory Limit: 64 MB
Time Limit: 1000 ms
Powered by:NEFU AB-IN
1217. 垒骰子
-
题意
赌圣atm晚年迷恋上了垒骰子，就是把骰子一个垒在另一个上边，不能歪歪扭扭，要垒成方柱体。
经过长期观察，atm 发现了稳定骰子的奥秘：有些数字的面贴着会互相排斥！
我们先来规范一下骰子：1 的对面是 4，2 的对面是 5，3 的对面是 6。
假设有 m 组互斥现象，每组中的那两个数字的面紧贴在一起，骰子就不能稳定的垒起来。
atm想计算一下有多少种不同的可能的垒骰子方式。
两种垒骰子方式相同，当且仅当这两种方式中对应高度的骰子的对应数字的朝向都相同。
由于方案数可能过多，请输出模 10^9+7 的结果。 -
思路
n较小时，可以用二维dp来做；n很大时，需要用矩阵快速幂来优化
-
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49'''
Author: NEFU AB-IN
Date: 2022-04-05 11:45:36
FilePath: \ACM\Acwing\1217.py
LastEditTime: 2022-04-05 15:40:46
'''
M = 6
MOD = int(1e9 + 7)
Matrix = lambda: [[0] * M for _ in range(M)]
def mul(a, b):
c = Matrix()
for i in range(M):
for j in range(M):
for k in range(M):
c[i][j] = (c[i][j] + a[i][k] * b[k][j]) % MOD
return c
def quickpow(a, b):
I = Matrix()
for i in range(M):
for j in range(M):
I[i][j] = (i == j)
while b:
if b & 1:
I = mul(I, a)
b >>= 1
a = mul(a, a)
return I
n, m = map(int, input().split())
A = [[4] * M for _ in range(M)] #一开始全是4，这样Fn * A = Fn+1
for i in range(m):
a, b = map(int, input().split())
a -= 1
b -= 1
A[a][(b + 3) % 6] = 0
A[b][(a + 3) % 6] = 0
B = quickpow(A, n - 1)
ans = 0
for i in range(M):
ans = (ans + 4 * sum(B[i])) % MOD
print(ans)
