蓝桥杯 垒骰子 （DP+矩阵快速幂）

蓝桥杯 垒骰子 （DP+矩阵快速幂）

赌圣atm晚年迷恋上了垒骰子，就是把骰子一个垒在另一个上边，不能歪歪扭扭，要垒成方柱体。经过长期观察，atm 发现了稳定骰子的奥秘：有些数字的面贴着会互相排斥！我们先来规范一下骰子：1 的对面是 4，2 的对面是 5，3 的对面是 6。假设有 m 组互斥现象，每组中的那两个数字的面紧贴在一起，骰子就不能稳定的垒起来。 atm想计算一下有多少种不同的可能的垒骰子方式。两种垒骰子方式相同，当且仅当这两种方式中对应高度的骰子的对应数字的朝向都相同。由于方案数可能过多，请输出模 10^9 + 7 的结果。不要小看了 atm 的骰子数量哦～

「输入格式」

第一行两个整数 n mn表示骰子数目接下来 m 行，每行两个整数 a b ，表示 a 和 b 数字不能紧贴在一起。

「输出格式」

一行一个数，表示答案模 10^9 + 7 的结果。

「样例输入」

2 11 2

「样例输出」

544

「数据范围」

对于 30% 的数据：n <= 5对于 60% 的数据：n <= 100对于 100% 的数据：0 < n <= 10^9, m <= 36

思路

​​dp[i][j]​​​ 代表高度为i，顶面点数为j的方案数，于是 ​​dp[i][j]​​ 就等于i-1高度时所有与j对面无冲突方案数的累加。

当然，最下面一层所有面在上的方案数都为1，求得结果后还要乘以 ​​4^i​​ ，因为每一个骰子都可以保证顶端点数不变的情况下四面旋转。

不过对于这道题1e9的数据O(n)的算法感觉还是会超时

于是使用了矩阵的方式来计算，关于矩阵列向量的选择求和与斐波那契数列相似。

构造出这样一个冲突矩阵之后便可以用矩阵快速幂的方法很快解决了，最终再与初始第一层的方案数相乘，便是结果。

只是因为网上找不到评测平台，所以代码的正确与否无法保证，不过思路就是这样啦！

Unkown代码

普通o(n)解法

#include#include#include#include#include#includeusing namespace std;#include#include#define mod 1000000007typedef __int64 LL;bool isc[7][7]; //存储冲突面LL mult(LL a,LL n) //数的快速幂 a^n{ LL ans=1; while(n) { if(n&1)ans=(ans*a)%mod; a=(a*a)%mod; n>>=1; } return ans;}int main(){ LL n,m; while(~scanf("%I64d%I64d",&n,&m)) { memset(isc,false,sizeof(isc)); for(int i=0; i

矩阵解法

#include#include#include#include#include#includeusing namespace std;#include#include#define mod 1000000007typedef __int64 LL;struct marx //定义矩阵{ int d[6][6]; marx() {} marx(int x) //构造：对角线赋值为x { memset(d,0,sizeof(d)); for(int i=0; i<6; i++) d[i][i]=x; }};marx mul(marx a,marx b) //矩阵乘法{ marx res=marx(0); //零 for(int i=0; i<6; i++) for(int j=0; j<6; j++) for(int s=0; s<6; s++) res.d[i][j]=((a.d[i][j]*b.d[j][s])%mod+res.d[i][j])%mod; return res;}LL sb;marx mult(marx t,LL n) //矩阵快速幂 t^n{ marx res=marx(1); //单位矩阵 LL ans=1,ss=4*4; //顺便计算了一下 4^n while(n) { if(n&1)res=mul(res,t),ans=(ans*ss)%mod; t=mul(t,t); ss=(ss*ss)%mod; n>>=1; } sb=ans; return res;}int main(){ LL n,m; while(~scanf("%I64d%I64d",&n,&m)) { marx isc,ans; for(int i=0; i<6; i++) { for(int j=0; j<6; j++) isc.d[i][j]=1; //初始化矩阵 ans.d[1][i]=1; //第一层各面情况 } int a,b; for(int i=0; i

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。