1217. 垒骰子

Powered by:NEFU AB-IN

Link

1217. 垒骰子

• 题意

  赌圣atm晚年迷恋上了垒骰子，就是把骰子一个垒在另一个上边，不能歪歪扭扭，要垒成方柱体。
  经过长期观察，atm 发现了稳定骰子的奥秘：有些数字的面贴着会互相排斥！
  我们先来规范一下骰子：1 的对面是 4，2 的对面是 5，3 的对面是 6。
  假设有 m 组互斥现象，每组中的那两个数字的面紧贴在一起，骰子就不能稳定的垒起来。
  atm想计算一下有多少种不同的可能的垒骰子方式。
  两种垒骰子方式相同，当且仅当这两种方式中对应高度的骰子的对应数字的朝向都相同。
  由于方案数可能过多，请输出模 10^9+7 的结果。

• 思路

  n较小时，可以用二维dp来做；n很大时，需要用矩阵快速幂来优化
  

• 代码

  '''
  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)