15年第六届蓝桥杯第九题_(矩阵快速幂优化的动态规划)

垒骰子

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

不要小看了 atm 的骰子数量哦～

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

「输出格式」
一行一个数，表示答案模 10^9 + 7 的结果。

「样例输入」
2 1
1 2

「样例输出」
544

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

资源约定：
峰值内存消耗 < 256M
CPU消耗 < 2000ms

---

感觉挺有难度的一题。。。最开始想到了动态规划，发现数据太大。。。

看了题解：博主最初用的常规dp，dp[i][j]：第i层，j点在上面的种数；dp[i][j]=dp[i][j]+dp[i-1][x](x的对面与j不冲突)，我最初的想法也跟这个差不多，只是时间复杂度不够。。。

然后看了楼主的第二篇用矩阵快速幂优化的解法，很精辟。http://blog.csdn.net/lonverce/article/details/45169285

可以用矩阵快速幂来优化一些不满足时间复杂度的dp，但是递推式很重要，想不出递推式都是白搭。。。

#include<iostream> #include<cstdio> #include<cstring> #include<vector> #include<algorithm> #include<string> using namespace std; #define MOD 1000000007 #define LL long long struct Matrix {int row,col;LL matr[8][8];Matrix() {}Matrix(int r,int c,int num){row=r;col=c;for(int i=1; i<=r; i++)for(int j=1; j<=c; j++)matr[i][j]=num;} };Matrix matr_multi(Matrix m1,Matrix m2) //矩阵乘法 {Matrix m3(m1.row,m2.col,0);for(int i=1; i<=m1.row; i++)for(int j=1; j<=m2.col; j++)for(int k=1; k<=m1.col; k++)m3.matr[i][j]=(m3.matr[i][j]+m1.matr[i][k]*m2.matr[k][j])%MOD;return m3; }void matr_givevalue(Matrix& a,Matrix b) {a.row=b.row;a.col=b.col;for(int i=1; i<=a.row; i++)for(int j=1; j<=a.col; j++)a.matr[i][j]=b.matr[i][j]; }Matrix matr_pow(Matrix m1,int k) //矩阵快速幂 {Matrix m2;matr_givevalue(m2,m1);k--;while(k>0){if(k&1)m2=matr_multi(m2,m1);m1=matr_multi(m1,m1);k>>=1;}return m2; }LL PowMod(LL n,int k) //常规快速幂 {LL res=1;while(k>0){if(k&1)res=(res*n)%MOD;n=(n*n)%MOD;k>>=1;}return res; }void matr_output(Matrix m) {for(int i=1; i<=m.row; i++){for(int j=1; j<=m.col; j++)cout<<m.matr[i][j]<<" ";cout<<endl;} } int main() {Matrix conflict(6,6,1);Matrix m2(1,6,1);int nn,mm;scanf("%d%d",&nn,&mm);for(int i=0; i<mm; i++){int a,b;scanf("%d%d",&a,&b);int bb=b+3,aa=a+3;if(bb>6)bb%=6;if(aa>6)aa%=6;conflict.matr[a][bb]=0; //设置conflict，这个地方要注意conflict.matr[aa][b]=0;}Matrix m1;m1=matr_pow(conflict,nn-1);m2=matr_multi(m2,m1);LL power=PowMod(4,nn);LL res=0;for(int i=1; i<=6; i++)res=(res+m2.matr[1][i])%MOD;res=(res*power)%MOD;printf("%I64d\n",res);return 0; }

 

转载于:https://www.cnblogs.com/jasonlixuetao/p/6491338.html

总结

以上是生活随笔为你收集整理的15年第六届蓝桥杯第九题_(矩阵快速幂优化的动态规划)的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。