头像

Cyan

四川成都

深度强化学习炼丹师

2015年第六届蓝桥杯省赛-I. 垒骰子

2015年第六届蓝桥杯省赛-I. 垒骰子

2021-12-16 · 94次阅读 · 原创 · 数据结构与算法

原题链接

题面

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

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

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

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

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

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

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

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

输入描述

输入第一行两个整数 n,m,n 表示骰子数目;

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

其中,0<n109,m360 < n \leq 10^9, m \leq 36

输出描述

输出一行一个数,表示答案模 109+7 的结果。

输入样例

2 1
1 2

输出样例

544

题解

矩阵快速幂,动态规划

从下到上一层一层的垒骰子,对于样例,1 和 2 不能接触,则以 4 为顶(1位底)的其下面一层不能以 2 为顶,以 5 为顶(2位底)的其下面一层不能以 1 为顶,记 f[i][j] 表示当前摆了 i 层骰子,且第 i 层的骰子以 j 为顶的方案数,则对于第一层:

f[1][1]=4f[1][2]=4f[1][3]=4f[1][4]=4f[i][5]=4f[i][6]=4f[1][1] = 4 \\ f[1][2] = 4 \\ f[1][3] = 4 \\ f[1][4] = 4 \\ f[i][5] = 4 \\ f[i][6] = 4

即第一层的每个数字为顶都有 4 种方案(因为除开顶面和底面,可以旋转 4 次,使侧面的数字不同),则摆一层总共有 24 总方案。

对于第二层:

f[2][1]=4×(f[1][1]+f[1][2]+f[1][3]+f[1][4]+f[1][5]+f[1][6])f[2][2]=4×(f[1][1]+f[1][2]+f[1][3]+f[1][4]+f[1][5]+f[1][6])f[2][3]=4×(f[1][1]+f[1][2]+f[1][3]+f[1][4]+f[1][5]+f[1][6])f[2][4]=4×(f[1][1]+f[1][3]+f[1][4]+f[1][5]+f[1][6])f[2][5]=4×(f[1][2]+f[1][3]+f[1][4]+f[1][5]+f[1][6])f[2][6]=4×(f[1][1]+f[1][2]+f[1][3]+f[1][4]+f[1][5]+f[1][6])f[2][1] = 4\times (f[1][1] + f[1][2] + f[1][3] + f[1][4] + f[1][5] + f[1][6]) \\ f[2][2] = 4\times (f[1][1] + f[1][2] + f[1][3] + f[1][4] + f[1][5] + f[1][6]) \\ f[2][3] = 4\times (f[1][1] + f[1][2] + f[1][3] + f[1][4] + f[1][5] + f[1][6]) \\ f[2][4] = 4\times (f[1][1] + f[1][3] + f[1][4] + f[1][5] + f[1][6]) \\ f[2][5] = 4\times (f[1][2] + f[1][3] + f[1][4] + f[1][5] + f[1][6]) \\ f[2][6] = 4\times (f[1][1] + f[1][2] + f[1][3] + f[1][4] + f[1][5] + f[1][6])

其中第二层以 4 为顶的 f[2][4] 的底面为 1,则其下面一层不能以 2 为顶,同理 f[2][5] 的底面为 1,下一层不能以 2 为顶,所以不用加上他们。乘 4 是因为当前固定最上层顶面的情况下,旋转侧面4次得到不同的4种方案。最终可以知道,摆两层共有 544 中方案。

则可以推导出下图面的矩阵乘法:

img

(上图中,A[i][j] 表示上层以数字 i 为顶,下层以数字 j 为顶的方案种类数。因为 1 和 2 不相贴,所以上层以 4 为顶时其底为 1, 则下层顶部不能为 2,则 A[4][2]=0A[4][2] = 0,同理 A[5][1]=0A[5][1] = 0f1[i] 代表第 1 层以 i 为顶的方案数,f2[i] 代表第 2 层以 i 为顶的方案数)

可以看出,由 f1 计算出 f2 只需要在 f1 左乘上一个系数矩阵A即可,而该矩阵是由两个面能否接触决定的,是已知的,则由此可以进行如下递推:

A×f1=f2A×A×f1=A×f2=f3A×A×A×f1=A×A×f2=A×f3=f4An1f1=fnA\times f_1 = f_2 \\ A\times A\times f_1 = A\times f_2 = f_3 \\ A\times A\times A\times f_1 = A\times A\times f_2 = A\times f_3 = f_4 \\ \cdots \\ A^{n - 1} f_1 = f_n

则可以知道摆放 n 层时,不同顶部数字的对应方案数,则本题需要用到矩阵的乘法运算,但此题 n 较大,最大可能有 109, 直接一层循环去累乘矩阵需要进行 109 次的矩阵乘法运算,肯定会超时。我们可以利用和 快速幂 相同的思路,改写为矩阵快速幂,以便在进行 log2n\log_2^n 次矩阵乘法运算即可得出答案。

先将 An1A^{n-1} 求出来后,再乘上第一层的6种基本方案数,则可以得到 n 层的不同顶部数字的方案数,再累加这6中不同顶部方案,可以得到最终的答案。

此题时间复杂度为 O(63×log2n)O(6^3 \times log_2^n),最坏情况下计算约 7000 次,完全能解决本题。具体详见代码。

代码

#include<bits/stdc++.h> using namespace std; const int MOD = 1e9 + 7, M = 7; int p[M] = {0, 4, 5, 6, 1, 2, 3}; //p[i] 表示数字 i 的对应面的数字 int n, m; struct Matrix { int v[M][M]; Matrix() { memset(v, 0, sizeof v); } void init() { //置为单位矩阵 for (int i = 1; i <= 6; i++) v[i][i] = 1; } Matrix operator*(const Matrix &b) { //重载矩阵的乘法运算 Matrix ans; for (int i = 1; i <= 6; i++) { for (int j = 1; j <= 6; j++) { int s = 0; for (int k = 1; k <= 6; k++) { s = (s + v[i][k] * 1ll * b.v[k][j]) % MOD; } ans.v[i][j] = s; } } return ans; } }; //矩阵快速幂 Matrix qpow(Matrix a, int n) { Matrix s; s.init(); while (n) { if (n & 1) s = s * a; a = a * a; n >>= 1; } return s; } int main() { cin >> n >> m; Matrix a, x; for (int i = 1; i <= 6; i++) { x.v[i][1] = 4; //第一层的每个数字为顶都有 4 中方案。 for (int j = 1; j <= 6; j++) a.v[i][j] = 4; //将系数矩阵 a 全置为 4 } for (int i = 0, x, y; i < m; i++) { scanf("%d%d", &x, &y); a.v[p[x]][y] = a.v[p[y]][x] = 0; //不能 x 和 y 不能接触, // 则以 x 为底的(以p[x]为顶)其下面一层不能以 y 为顶 // 同理,以 y 为底的(以p[y]为顶)其下面一层不能以 x 为顶 } Matrix b = qpow(a, n - 1) * x; int ans = 0; //累加 n 层6种不同顶部的方案数即为最终结果 for (int i = 1; i <= 6; i++) ans = (ans + b.v[i][1]) % MOD; cout << ans << endl; return 0; }

标题: 2015年第六届蓝桥杯省赛-I. 垒骰子
链接: https://www.fightingok.cn/detail/178
更新: 2022-09-18 22:45:45
版权: 本文采用 CC BY-NC-SA 3.0 CN 协议进行许可