P8624 垒骰子

P8624 [蓝桥杯 2015 省 AB] 垒骰子

题目描述

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

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

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

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

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

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

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

不要小看了 atm 的骰子数量哦～。

输入格式

第一行两个整数 $n$，$m$。

$n$ 表示骰子数目。

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

输出格式

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

输入输出样例 #1

输入 #1

2 1
1 2

输出 #1

544

说明/提示

对于 $30\%$ 的数据：$n\le 5$。

对于 $60\%$ 的数据：$n\le 100$。

对于 $100\%$ 的数据：$0<n\le 10^9,m\le 36$。

时限 2 秒, 256M

蓝桥杯 2015 年省赛 AB 组 I 题。

解析

这是一个经典的矩阵快速幂题目。

问题核心

我们要把 $n$ 个骰子垒起来，每一层的骰子有 6 种朝上的面。确定了朝上的面，朝下的面也就确定了。 每一层骰子的放置受制于下面一层骰子的朝上面（必须与当前层的朝下面不互斥）。 同时，每一层骰子除了上下面的朝向确定外，侧面还可以有 4 种旋转方向。

状态转移

假设 $dp[i][j]$ 表示垒了 $i$ 个骰子，且最上面那个骰子（第 $i$ 个）朝上的面是 $j$ 的方案数。 那么第 $i$ 个骰子的朝下面就是 $opposite[j]$。 它能垒在第 $i-1$ 个骰子上，前提是第 $i-1$ 个骰子的朝上面 $k$ 与 $opposite[j]$ 不互斥。 而且，对于每一种合法的连接，第 $i$ 个骰子都可以有 4 种侧向旋转方式。

转移方程： $dp[i][j]={\sum }_{k=1}^6(dp[i-1][k]\times 4)$ 其中要求 $k$ 和 $opposite[j]$ 不互斥。

矩阵加速

由于 $n$ 高达 $10^9$，简单的 $O(n)$ 递推会超时。观察转移方程，这是一个线性递推关系，可以用矩阵快速幂加速。

构造一个 $6\times 6$ 的转移矩阵 $Base$。 $Base[j][k]$ 表示从“上一层顶面为 $k$”转移到“当前层顶面为 $j$”的方案倍数。 如果上一层顶面 $k$ 和当前层底面 $opposite[j]$ 不互斥，则 $Base[j][k]=4$（因为有4种旋转）。 否则 $Base[j][k]=0$。

初始向量 $Init$ 为垒 1 个骰子的情况。1 个骰子时，任意面 $j$ 朝上都有 4 种方案（侧面旋转），所以初始状态每个面都是 4。但为了方便矩阵运算，我们通常直接计算 $Bas{e}^{n-1}$，然后统计所有元素的和再乘 4。

最终答案计算

设最终矩阵 $Res=Bas{e}^{n-1}$。 由于第 1 个骰子不管是哪个面朝上，基础方案都是 4（侧面旋转），且不需要和地面判互斥。 所以总方案数 = $({\sum }_{r=1}^6{\sum }_{c=1}^{6}Res[r][c])\times 4$。

代码

//
// Created by 23264 on 2026/2/12.
//
#include<bits/stdc++.h>
using namespace std;
 
typedef long long ll;
constexpr int MOD = 1e9 + 7;
 
// 骰子对立面映射
// 面 1 对 4，2 对 5，3 对 6
// 下标 0 1 2 3 4 5 6
// 对立 0 4 5 6 1 2 3
int op[7] = {0,4,5,6,1,2,3};
 
// 互斥表
bool conflict[7][7];
 
struct Matrix
{
    ll mat[7][7]{};
    Matrix()
    {
        memset(mat,0,sizeof(mat));
    }
};
 
// 矩阵乘法
Matrix multiply(const Matrix& a,const Matrix& b)
{
    Matrix c;
    for (int i = 1;i <= 6;i++)
    {
        for (int j = 1;j <= 6;j++)
        {
            for (int k = 1;k <= 6;k++)
            {
                c.mat[i][j] = (c.mat[i][j] + a.mat[i][k] * b.mat[k][j]) % MOD;
            }
        }
    }
    return c;
}
 
// 矩阵快速幂
Matrix power(Matrix a,int n)
{
    Matrix res;
    // 初始化单位矩阵
    for (int i = 1;i <= 6;i++)
    {
        res.mat[i][i] = 1;
    }
 
    while (n > 0)
    {
        if (n & 1)
        {
            res = multiply(res,a);
        }
        a = multiply(a,a);
        n >>= 1;
    }
    return res;
}
 
int main()
{
    // 优化输入输出
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int n,m;
    cin >> n >> m;
 
    // 读入互斥关系
    for (int i = 0;i < m;i++)
    {
        int u,v;
        cin >> u >> v;
        conflict[u][v] = true;
        conflict[v][u] = true;
    }
 
    // 构建转移矩阵
    Matrix base;
    for (int i = 1;i <= 6;i++)
    {       // i 是当前骰子朝上的面
        for (int j = 1;j <= 6;j++)
        {   // j 是下面骰子朝上的面
            // 当前骰子的朝下面是 op[i]
            // 如果下面骰子的朝上面 j 与 当前骰子的朝下面 op[i] 不互斥
            if (!conflict[j][op[i]])
            {
                base.mat[i][j] = 4; // 有4种旋转可能
            }
            else
            {
                base.mat[i][j] = 0;
            }
        }
    }
 
    // 计算 Matrix^(n-1)
    // 如果 n=1，power(base, 0) 返回单位矩阵，后续求和结果为 6，最后乘 4 得到 24，正确
    Matrix res = power(base,n - 1);
    ll ans = 0;
    // 统计矩阵所有元素的和
    // 逻辑解释：
    // 初始状态（第1层）是一个全为4的向量 V1 = [4, 4, 4, 4, 4, 4]^T
    // Vn = Base^(n-1) * V1
    // 我们要求的是 Vn 所有元素的和
    // 这等价于 Base^(n-1) 的所有元素之和 乘以 4
    ll sum_matrix = 0;
    for (int i = 1;i <= 6;i++)
    {
        for (int j = 1;j <= 6;j++)
        {
            sum_matrix = (sum_matrix + res.mat[i][j]) % MOD;
        }
    }
    ans = (sum_matrix * 4) % MOD;
    cout << ans << endl;
}