欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

程序员文章站 2022-06-04 12:24:34
...

第九题垒骰子

赌圣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
2015年蓝桥杯省赛B组真题 第九题垒骰子

测试样例2:
4 3
6 5
3 1
5 4
输出:186880
2015年蓝桥杯省赛B组真题 第九题垒骰子
一个上午过去了啥也没干就做了这一道题,我是真菜。

 #include<stdio.h>
 #include<string.h>
 
 
 typedef 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;
			else
			    k.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;
 }