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<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;
}
上一篇: 快速幂