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

ReturnXI · 2024-04-11 09:27:58 · 题解

这个题目题解较少，过来水一篇题解

思路分析

当涉及骰子堆叠时，我们可以考虑使用动态规划来解决这个问题。我们将定义一个动态规划数组 dp[i][j][k]，表示在堆叠前 i 个骰子时，第 i 个骰子的朝向为 j，且共有 k 种排列方式。由于题目中要求的是堆叠骰子的方式总数，因此我们只需要考虑每个骰子的朝向即可。

接下来，我们定义状态转移方程来更新 dp 数组。假设当前处理的是第 i 个骰子，其朝向为 j，我们需要计算在前 i 个骰子堆叠完成后，朝向为 j 的方案数 dp[i][j][k]。考虑到每个骰子有六个面，我们可以遍历上一个骰子的朝向 l，来更新当前骰子的状态。如果上一个骰子的朝向为 l,那么当前骰子的朝向只能为1-6中与 l 不相邻的数。在更新状态时，需要考虑题目中的排斥关系。

根据上述思路，我们可以得到状态转移方程如下：

其中，状态转移方程中的求和操作表示在上一个骰子的朝向为 l 的情况下，当前骰子的朝向为 j 的排列方式总数。在求解 dp 数组时，我们需要考虑排斥关系，即不能将相互排斥的数字紧贴在一起。因此，在更新状态时，需要检查上一个骰子的朝向 l 和当前骰子的朝向 j 是否满足排斥关系。

然后，我们可以通过填充 dp 数组来计算堆叠所有骰子的方式总数。当堆叠完成后，我们将得到 dp[n][j][k] 中所有朝向和为 k 的排列方式总数之和即为最终的答案。

最后，我们需要对最终的答案取模。

综上所述，我们可以使用动态规划的方法来解决这个问题。具体实现细节如下：

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int MOD = 1e9+7;
int opposite[7] = {0, 4, 5, 6, 1, 2, 3}; // 确定骰子的对立面
int n, m;

// 构造一个矩阵类
struct Matrix { 
    ll data[6][6];
    Matrix() { 
        for(int i = 0; i < 6; i++) {
            for(int j = 0; j < 6; j++) {
                data[i][j] = 1;
            }
        }
    }
};

// 矩阵乘法
Matrix multiply(Matrix m1, Matrix m2) { 
    Matrix result;
    for(int i = 0; i < 6; i++) {
        for(int j = 0; j < 6; j++) {
            result.data[i][j] = 0;
            for(int k = 0; k < 6; k++) {
                result.data[i][j] = (result.data[i][j] + m1.data[i][k] * m2.data[k][j]) % MOD;
            }
        }
    }
    return result;
}

// 用快速幂求矩阵
Matrix power(Matrix m, int k) { 
    Matrix result;
    for(int i = 0; i < 6; i++) {
        for(int j = 0; j < 6; j++) {
            if(i == j) {
                result.data[i][j] = 1;
            } else {
                result.data[i][j] = 0;
            }
        }
    }
    while(k) {
        if(k & 1) {
            result = multiply(result, m);
        }
        m = multiply(m, m);
        k >>= 1;
    }
    return result;
}

ll quick_power(ll a, ll b) {
    ll result = 1;
    while(b) {
        if(b & 1) {
            result = (result * a) % MOD;
        }
        a = (a * a) % MOD;
        b >>= 1;
    }
    return result;
}

int main() {
    cin >> n >> m;
    Matrix conflict_matrix; // 冲突矩阵
    for(int i = 1; i <= m; i++) {
        int a, b;
        cin >> a >> b;
        conflict_matrix.data[opposite[a] - 1][b - 1] = 0; // 若1，2冲突，那冲突矩阵的4，2和5，1这两个位置就应该是0，因为矩阵的行代表朝上的数字，所以如果4朝上，1就朝下，会和2冲突.
        conflict_matrix.data[opposite[b] - 1][a - 1] = 0; 
    }
    Matrix conflict_n_minus_1 = power(conflict_matrix, n - 1); // 求冲突矩阵的n-1次方
    ll sum = 0;
    for(int i = 0; i < 6; i++) { // 求出所有的方案数，求出冲突矩阵的n-1次方后，再乘一个元素全为1的1行6列的矩阵，这个矩阵是最开始数字1~6朝上的方案数，都为1，又因为每个都是乘1，所以只要算最后冲突矩阵的每个元素总和
        for(int j = 0; j < 6; j++) {
            sum = (sum + conflict_n_minus_1.data[i][j]) % MOD;
        }
    }

    ll ans = (sum * quick_power(4, n)) % MOD; // 快速幂
    cout << ans << endl;
    return 0;
}

如果后续发现有问题会及时更改的。