题目：
题目描述
赌圣atm晚年迷恋上了垒骰子，就是把骰子一个垒在另一个上边，不能歪歪扭扭，要垒成方柱体。 经过长期观察，atm 发现了稳定骰子的奥秘：有些数字的面贴着会互相排斥！ 我们先来规范一下骰子：1 的对面是 4，2 的对面是 5，3 的对面是 6。 假设有 m 组互斥现象，每组中的那两个数字的面紧贴在一起，骰子就不能稳定的垒起来。 atm想计算一下有多少种不同的可能的垒骰子方式。 两种垒骰子方式相同，当且仅当这两种方式中对应高度的骰子的对应数字的朝向都相同。 由于方案数可能过多，请输出模 10^9 + 7 的结果。
输入格式
输入存在多组测试数据，对于每组数据： 第一行两个整数 n m(0 输出格式 对于每组测试数据，输出一行，只包含一个数，表示答案模 10^9 + 7 的结果。 输入样例 2 1 1 2 输出样例 544 思路： 递归和递推可以写出来，但是不能通过所有数据，会超时，这道题主要是一个骰子放另一个骰子上面的时候，可以转动，就等于最后每个骰子*4%mod就是结果 代码（递归）： #include #define MOD 1000000009 #define IOS ios::sync_with_stdio(false), cin.tie(0), cout.tie(0) using namespace std; int mp[7]; bool c[7][7]; int init() { mp[1]=4; mp[4]=1; mp[2]=5; mp[3]=6; mp[6]=3; mp[5]=2; } int fun(int i,int cot) { if(cot==0) return 4; long long ans=0; for(int j=1;j<=6;j++) { if(c[mp[i]][j]) continue; else ans=(ans+fun(j,cot-1))%MOD; } return ans; } int main() { IOS; int n,m,a,b; init(); while(cin>>n>>m) { for(int i=0;i { cin>>a>>b; c[a][b]=1; c[b][a]=1; } long long ans=0; for(int i=1;i<=6;i++) { ans=(ans+4*fun(i,n-1))%MOD; } cout< } } 代码（动态规划+快速幂） #include #define mod 1000000007 #define IOS ios::sync_with_stdio(false), cin.tie(0), cout.tie(0) using namespace std; long long dp[2][7];//二维滚动数组，i层，每层朝上的点数 int n,m,mp[7]; bool c[7][7]; int init() { mp[1]=4; mp[4]=1; mp[2]=5; mp[3]=6; mp[6]=3; mp[5]=2; } int main() { IOS; int n,m,a,b; init(); while(cin>>n>>m) { for(int i=0;i { cin>>a>>b; c[a][b]=1; c[b][a]=1; } for(int i=1;i<=6;i++) dp[0][i]=1;//初始化滚动数组使第一层每种方案都能用 int cur=0;//迭代层数 for(int i=2;i<=n;i++) { cur=1-cur; for(int j=1;j<=6;j++) { dp[cur][j]=0; for(int k=1;k<=6;k++) { if(c[mp[j]][k]) continue; else dp[cur][j]=(dp[cur][j]+dp[1-cur][k])%mod; } } } long long sum=0; for(int i=1;i<=6;i++) { sum=(sum+dp[cur][i])%mod; } //快速幂，求4的n次方 long long ans=1; long long tmp=4; long long p=n; while(p!=0) { if(p&1==1) ans=(ans*tmp)%mod; tmp=(tmp*tmp)%mod; p>>=1; } cout<<(sum*ans)%mod< } } 代码（矩阵快速幂）： 我能力有限，一时半会还理解不了这种 [蓝桥杯2015初赛]垒骰子（从dp到矩阵快速幂的优化）_zaiyang遇见-CSDN博客