[蓝桥杯2015初赛]垒骰子

问题

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

经过长期观察,atm 发现了稳定骰子的奥秘:有些数字的面贴着会互相排斥! 我们先来规范一下骰子:1 的对面是 4,2 的对面是 5,3 的对面是 6。 

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

atm想计算一下有多少种不同的可能的垒骰子方式。 两种垒骰子方式相同,当且仅当这两种方式中对应高度的骰子的对应数字的朝向都相同。 

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

输入

存在多组测试数据,对于每组数据: 第一行两个整数 n m([蓝桥杯2015初赛]垒骰子,[蓝桥杯2015初赛]垒骰子)  n表示骰子数目 接下来 m 行,每行两个整数 a b ,表示 a 和 b 数字不能紧贴在一起。 

输出

对于每组测试数据,输出一行,只包含一个数,表示答案模 10^9 + 7 的结果。 

链接:垒骰子


题解

这道题涉及快速幂的相关算法,如果对于该算法不熟悉,可以参考这篇博客:快速幂取模

首先看数据量,[蓝桥杯2015初赛]垒骰子,可以发现这道题只能用[蓝桥杯2015初赛]垒骰子的算法可以在规定时间内求解。而常用的[蓝桥杯2015初赛]垒骰子算法是二分算法和快速幂的算法,根据题意,显然二分算法并不适用于这题,因此我们应该往快速幂的方向去求解。

然后我们来模拟一下垒骰子的过程:第一个骰子我们可以选择任何一面朝上,接着第二个骰子需要垒在第一个骰子之上,假设没有互斥的情况,那么它有6个选择来垒在第一个骰子上,再考虑第三个骰子,也是6个选择垒在第二个骰子上,接下来的所有的骰子都是一样的。

一旦我们确定了所有的骰子在竖直方向上的组合方式后,我们还可以通过改变每个骰子的数字朝向来得到不同的组合方式,一个骰子可以改变4个朝向,因此n个骰子的朝向总数为[蓝桥杯2015初赛]垒骰子

因此设竖直方向上的组合方式总数为ans,则垒骰子的方案总数为 [蓝桥杯2015初赛]垒骰子

综上,我们只需求出竖直方向上的组合方式的递推式,然后转换为矩阵快速幂来求即可,改变每个骰子的数字朝向可以用快速幂取模来求解。

设 [蓝桥杯2015初赛]垒骰子  为第 i 层 k 朝上的方案数, 则递推式为 [蓝桥杯2015初赛]垒骰子( k 朝上 与 j 朝上 不冲突,[蓝桥杯2015初赛]垒骰子)。

得到递推式之后,我们需要一个矩阵T,来实现前后状态的转换,假设冲突面为1,2,那么得到的冲突矩阵T及转换公式为

[蓝桥杯2015初赛]垒骰子

由于定义的是朝上的面,因此我们应该将冲突矩阵中的冲突面的对立面的相应数字置为0,如冲突面为1,2,则只有当4朝上的时候,1才朝下,因此将4中的2置为0,意为与2冲突。

因此我们只需计算矩阵[蓝桥杯2015初赛]垒骰子即可。


完整代码

#include <iostream>
#include <cstring>
#include <cstdlib>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#define ll long long
#define maxn 7
#define mod 1000000007
using namespace std;
struct Matrix
{
  ll m[maxn][maxn];
  Matrix()
  {
    for(int i = 1; i < maxn; i++)
      for(int j = 1; j < maxn; j++)
    {
      m[i][j] = 1;
    }
  }
};
int op[maxn];
Matrix Mpow(Matrix m1, Matrix m2)
{

  Matrix ans;
  memset(ans.m, 0, sizeof(ans.m));

  for(int i = 1; i < maxn; i++)
    for(int j = 1; j < maxn; j++)
      for(int k = 1; k < maxn; k++)
          ans.m[i][j] = (ans.m[i][j] + (m1.m[i][k] % mod * m2.m[k][j] % mod) % mod) % mod;

  return ans;
}
Matrix quickMod(Matrix a, ll b)
{
  Matrix ans;
  memset(ans.m, 0, sizeof(ans.m));
  for(int i = 1; i < maxn; i++) ans.m[i][i] = 1;

  while(b)
  {
    if(b&1) ans = Mpow(ans, a);
    b = b >> 1;
    a = Mpow(a, a);
  }

  return ans;
}
void init()
{
  op[1] = 4;
  op[2] = 5;
  op[3] = 6;
  op[4] = 1;
  op[5] = 2;
  op[6] = 3;
}
int main()
{

  int n, m;
  init();
  while(cin >> n >> m)
  {
    Matrix s;
    for(int i = 1; i <= m; i++)
    {
      int a, b;
      cin >> a >> b;
      s.m[op[a]][b] = s.m[op[b]][a] = 0;
    }
    s = quickMod(s, n-1);

    long long ans = 0;
    for(int i = 1; i < maxn; i++)
      for(int j = 1; j < maxn; j++)
        ans = (ans + s.m[i][j]) % mod;

    long long tmp = 1;
    long long a = 4;
    while(n)
    {
      if(n&1) tmp = (tmp % mod * a % mod) % mod;
      n = n >> 1;
      a = (a % mod * a % mod) % mod;
    }

    cout << (ans%mod * tmp%mod) % mod << endl;
  }



  return 0;
}

 

上一篇:2014年度辛星css教程夏季版第二节


下一篇:科研绘图 | SCI发表必须要注意的插图规范!