2015年蓝桥杯省赛B组真题 第九题垒骰子

第九题垒骰子

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

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

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

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

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

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

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

输入格式
第一行包含两个整数 n,m，分别表示骰子的数目和排斥的组数。

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

输出格式
共一个数，表示答案模 109+7 的结果。

数据范围
1≤n≤109,
1≤m≤36,
1≤a,b≤6
输入样例：
2 1
1 2
输出样例：
544

看了蓝桥杯老师讲解的视频再写的。OJ连接
递归和动归都会超时，所以需要把复杂度降到O（n）以下，正解：矩阵快速幂
思路：与其他的矩阵快速幂一样，主要在于如何构建矩阵，
首先第一层最下面有6种朝向（1，2，3，4，5，6），每种朝向又可以偏移4次，所以arr[6]={4,4,4,4,4,4};表示第一个塞子的情况。递推矩阵M[6][6];
（第一个6表示当前骰子数字那个朝上，第二个6表示前一个骰子那个数字朝上具体看下面的列子） F[n]=arr*M^(N-1)
举例：测试样例：
2 1
1 2
输出：544

测试样例2：
4 3
6 5
3 1
5 4
输出：186880

 #include#includetypedef long long ll;ll mod=1000000007;int p[7][7];//记录冲突 int dd[6]={3,4,5,0,1,2};//记录对立面 struct Matrix{ll mat[6][6];//冲突矩阵Matrix(){for(int i=0;i<6;i++){for(int j=0;j<6;j++){mat[i][j]=4;//因为可以转动4个面 }}} };Matrix fun(Matrix A,Matrix B)//两个矩阵相乘 
{Matrix res;memset(res.mat,0,sizeof(res.mat));for(int i=0;i<6;i++){for(int j=0;j<6;j++){for(int k=0;k<6;k++){res.mat[i][j]=(res.mat[i][j]+A.mat[i][k]*B.mat[k][j])%mod;}}}return res;
}Matrix fun1(ll n,Matrix ans)//矩阵快速幂 
{Matrix res;memset(res.mat,0,sizeof(res.mat));for(int i=0;i<6;i++)res.mat[i][i]=1;//构造单位矩阵 while(n){if(n%2==1)res=fun(res,ans);ans=fun(ans,ans);n/=2;}return res;
}int main(){ll n,m;//骰子数和冲突数scanf("%lld%lld",&n,&m); for(int i=0;i<m;i++){int a,b;scanf("%d%d",&a,&b);a--,b--;p[dd[b]][a]=1;//表示有冲突 p[dd[a]][b]=1; } int arr[6]={4,4,4,4,4,4};//表示第一个骰子的6种不同的朝向情况 Matrix k;//冲突矩阵 for(int i=0;i<6;i++){for(int j=0;j<6;j++){if(p[i][j]==0)k.mat[i][j]=4;elsek.mat[i][j]=0;}}k=fun1(n-1,k);//最后得到的冲突矩阵和arr【】相乘 ll ss=0;for(int i=0;i<6;i++){for(int j=0;j<6;j++){ss=(ss+k.mat[i][j]*arr[j])%mod;}}printf("%lld",ss);return 0;} 

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！