题目描述

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

输入

输入存在多组测试数据，对于每组数据： 第一行两个整数 n m(0<n<10^9,m<=36) n表示骰子数目 接下来 m 行，每行两个整数 a b ，表示 a 和 b 数字不能紧贴在一起。

输出

对于每组测试数据，输出一行，只包含一个数，表示答案模 10^9 + 7 的结果。 样例输入 2 1 1 2 样例输出 544

【想说的】初看题目，有一句话要注意“当且仅当这两种方式中对应高度的骰子的对应数字的朝向都相同。”说明一个骰子摆好之后，还可以转动，这样也是不同的情况。敲定摆的方式之后，每个骰子还需要乘以4。一共有三种解题方法（递归，动态规划，矩阵快速幂），代表三种水平，也对应三种方式。我来一一讲述一下吧。

1.递归（只能过小数据）

ans_i =$\sum _1^6$ans_i-1层数量（除去冲突的）*4 (第i层骰子摆放后的，不同数量）=把1~6数字朝上的和 （每种数字的情况还要×4） 相当于确定了上一个骰子的上下两面是什么，递归来放下一个骰子，直到0，返回4，相当于没有骰子可以垒了就是一种情况，考虑转面的情况，所以返回4。

#include <bits/stdc++.h> #define ll long long using namespace std; const int mod=1e9+7; int md[7]; int cf[7][7]; void init() { md[1]=4; md[4]=1; md[2]=5; md[5]=2; md[3]=6; md[6]=3; } ll f(int x,int y) { if(y==0) return 4; ll ans=0; for(int i=1;i<=6;i++) { if(cf[md[x]][i]==1) continue; ans=(ans+f(i,y-1))%mod; } return ans; } int main() { int n,m; scanf("%d%d",&n,&m); init(); memset(cf,0,sizeof cf); for(int i=0;i<m;i++) { int a,b; scanf("%d%d",&a,&b); cf[a][b]=1; cf[b][a]=1; } ll ans=0; for(int i=1;i<=6;i++) { ans=(ans+f(i,n-1)*4)%mod; } cout<<ans<<endl; }

2.动态规划（递推，过一般般数据）

上面递归的思想是从上往下看，那么动态规划就是从下往上看（有点逆向的感觉），dp[i][j]表示第i层，j朝上的摆放数量，动态规划的式子是：（j=1) dp[i][j]=$\sum _j^6$dp[i-1][j] 并且j的对面和i不会冲突 并且这个动态规划也不用开大数组去存，只要两层就好了，互相滚动就好了，用一个int cur；cur=1-cur;(实现0，1互换的效果） 最后结果等于迭代的最后一层dp加起来。还要考虑一下，转面乘以4的那种，直接最后乘以4的n次方，因为有n个骰子，每个骰子都要乘以4.

#include <bits/stdc++.h> #define ll long long using namespace std; const int mod=1e9+7; int md[7]; int cf[7][7]; int dp[2][7]; void init() { md[1]=4; md[4]=1; md[2]=5; md[5]=2; md[3]=6; md[6]=3; } ll qmi(int x,int y) { ll ans=1; while(y>0) { if(y&1) ans=(ans*x)%mod; y>>=1; x=(x*x)%mod; } return ans; } int main() { int n,m; scanf("%d%d",&n,&m); init(); memset(cf,0,sizeof cf); for(int i=0;i<m;i++) { int a,b; scanf("%d%d",&a,&b); cf[a][b]=1; cf[b][a]=1; } int cur=0; for(int i=1;i<=6;i++) { dp[cur][i]=1; } for(int k=2;k<=n;k++) { cur=1-cur; for(int i=1;i<=6;i++) { dp[cur][i]=0; for(int j=1;j<=6;j++) { if(cf[md[i]][j]!=1) { dp[cur][i]=(dp[cur][i]+dp[1-cur][j])%mod; } } } } ll ans=0; for(int i=1;i<=6;i++) { ans=(ans+dp[cur][i])%mod; } // cout<<ans<<endl; ans=ans*qmi(4,n)%mod; cout<<ans<<endl; }

3.矩阵快速幂（很快求解）

有没有很快的方法得到那个n次的结果呢，其实仔细想一想，这种叠加关系，有点像矩阵乘法，虽然我一开始可能get不到这个点，但是这个做法还是很奇妙的。

#include <bits/stdc++.h> #define ll long long using namespace std; const int mod=1e9+7; int md[7]; void init() { md[1]=4; md[4]=1; md[2]=5; md[5]=2; md[3]=6; md[6]=3; } struct M{ ll m[7][7]; M(){ for(int i=0;i<6;i++) { for(int j=0;j<6;j++) { m[i][j]=1; } } } }; M mul(M a,M b) { M ans; for(int i=0;i<6;i++) { for(int j=0;j<6;j++) { ans.m[i][j]=0; for(int k=0;k<6;k++) { ans.m[i][j]=(ans.m[i][j]+a.m[i][k]*b.m[k][j])%mod; } } } return ans; } M qmi(M x,int y) { M ans; for(int i=0;i<6;i++) { for(int j=0;j<6;j++) { if(i==j) ans.m[i][j]=1; else ans.m[i][j]=0; } } while(y>0) { if(y&1) ans=mul(ans,x); x=mul(x,x); y>>=1; } return ans; } ll qqmi(ll x,ll y) { ll ans=1; while(y>0) { if(y&1) ans=(ans*x)%mod; x=(x*x)%mod; y>>=1; } return ans; } int main() { int n,m; scanf("%d%d",&n,&m); init(); M ma; for(int i=0;i<m;i++) { int a,b; scanf("%d%d",&a,&b); ma.m[md[a]-1][b-1]=0; ma.m[md[b]-1][a-1]=0; } M mb=qmi(ma,n-1); ll t=0; for(int i=0;i<6;i++) { for(int j=0;j<6;j++) { t=(t+mb.m[i][j])%mod; } } printf("%lld\n",(t*qqmi(4,n))%mod); return 0; }