我不是张玉想

用户名：ZYX666

访问量：5832

签　名：

---------------------------靓仔靓铝分割线---------------------------

等　　级
排　　名	699
经　　验	3926
参赛次数	8
文章发表	13
年　　龄	0
在职情况	学生
学　　校	东华理工大学
专　　业	计算机科学与技术

　　自我简介：

TA的其他文章

我不是张玉想——棋盘多项式-题解（C++代码）
浏览：353

我不是张玉想——公交汽车-题解（C++代码）
浏览：951

我不是张玉想——新生舞会-题解（C++map容器解题代码）
浏览：395

你可能喜欢

我不是张玉想——垒骰子-题解（C++代码）

　　作者: 我不是张玉想　　　　发表时间：2020-08-28 14:09:25 浏览：366　|　评论：0　

原题链接：蓝桥杯2015年第六届真题-垒骰子

## 一、解题思路：
#### 1、暴力、动态规划（只得22分）：时间复杂度o(n)，n太大还是超时
#### 2、看别人博客了解到要用矩阵快速幂，但菜鸡的我没有听过，所以我就去B站学了快速幂、矩阵快速幂，学完后重新做了一遍，过了，开心
#### 3、快速幂、矩阵快速幂这里就不详细讲解了，怕误人子弟，推荐不会这个算法的同志一定要学下。
![](/image_editor_upload/20200828020837_94339.jpg)
#### 4、不要盲目的只刷会做的题哦，正所谓刷四五道水题不如花时间做一道难题，学习新的算法，方可提高，加油。
## 二、完整代码（仅供参考，欢迎提出建议和指正）
```cpp
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<cstring>
#include<vector>
#include<deque>
#include<set>
#include<stack> 
#include<cmath>
#include<time.h>
#include<iomanip>

using namespace std;
typedef long long int ll;

const ll MOD = 1e9+7;
#define mod(x) x%MOD

typedef struct MAT{//矩阵结构体
	ll dp[7][7];
	ll row=6;
	ll colum=6;
	MAT(){
		for(int i=1;i<=6;i++)
			for(int j=1;j<=6;j++)
				dp[i][j]=4;
	}
}mat;

ll mat_sum(mat a){//求矩阵元素和
	ll ans=0;
	for(int i=1;i<=a.row;i++){
		for(int j=1;j<=a.colum;j++){
			ans=mod(ans+a.dp[i][j]);
		}
	}
	return ans;
}

mat operator*(mat a,mat b){//重载*，用以计算矩阵相乘
	mat temp;
	temp.row=a.row;
	temp.colum=b.colum;
	for(int i=1;i<=a.row;i++){
		for(int j=1;j<=a.colum;j++){
			ll x = 0;
			for(int k=1;k<=b.colum;k++){
				x =	mod(x+a.dp[i][k]*b.dp[k][j]);
			}
			temp.dp[i][j] = mod(x);
		}
	}
	return temp;
}

mat mat_pow(mat a,ll p){//矩阵快速幂
	mat ans;
	for(int i=1;i<=ans.row;i++)
		for(int j=1;j<=ans.colum;j++)
				ans.dp[i][j]=i==j;
				
	while(p){
		if(p&1){
			ans = ans*a;
		}
		a = a*a;
		p>>=1;
	}
	return ans;
}

int main()
{
	int face[7]={0,4,5,6,1,2,3};
	int n,m;
	cin>>n>>m;
	if(n==1){
		cout<<24;
		return 0;
	}
	
	mat a;
	mat b;
	b.row=1;
			
	for(int i=0;i<m;i++){
		int x,y;
		cin>>x>>y;
		//这里需要小心，之前这里没考虑清楚，导致一直为啥结果错误
		a.dp[x][face[y]]=0;
		a.dp[y][face[x]]=0;
	}
	
	mat temp1 = mat_pow(a,n-1);//权值矩阵做快速幂
 	mat temp2 = b*temp1;//第一层方案数矩阵乘以权重矩阵结果
	ll ans = mod(mat_sum(temp2));//上面矩阵结果把元素相加就是总方案数
	cout<<ans;
	return 0;
}
```
##### PS：以上为本人拙见，若有错误或更好的方法，望大家不吝赐教，共同进步，十分感谢！！！

0.0分

4 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

我不是张玉想

TA的其他文章

你可能喜欢

C二级辅导-求偶数和（C++代码）

弟弟的作业（C++代码）

C语言程序设计教程（第三版）课后习题6.7 （C语言代码）

C语言程序设计教程（第三版）课后习题6.3 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

我不是张玉想——垒骰子-题解（C++代码）

评论区

精彩推荐

P1001 （C语言代码）

C语言程序设计教程（第三版）课后习题6.4 （C语言代码）

简单的a+b （C语言代码）

P1000 （C语言代码）

川哥的吩咐（C语言代码）

矩阵的对角线之和（C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

字符串的修改（C语言代码）

三角形（C语言代码）

母牛的故事（C语言代码）

我不是张玉想

TA的其他文章

你可能喜欢

C二级辅导-求偶数和 （C++代码）

弟弟的作业 （C++代码）

C语言程序设计教程（第三版）课后习题6.7 （C语言代码）

C语言程序设计教程（第三版）课后习题6.3 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

我不是张玉想——垒骰子-题解（C++代码）

评论区

精彩推荐

P1001 （C语言代码）

C语言程序设计教程（第三版）课后习题6.4 （C语言代码）

简单的a+b （C语言代码）

P1000 （C语言代码）

川哥的吩咐 （C语言代码）

矩阵的对角线之和 （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

字符串的修改 （C语言代码）

三角形 （C语言代码）

母牛的故事 （C语言代码）

C二级辅导-求偶数和（C++代码）

弟弟的作业（C++代码）

　　评论区

川哥的吩咐（C语言代码）

矩阵的对角线之和（C语言代码）

字符串的修改（C语言代码）

三角形（C语言代码）

母牛的故事（C语言代码）