蓝桥杯真题-垒骰子
赌圣atm晚年迷恋上了垒骰子，就是把骰子一个垒在另一个上边，不能歪歪扭扭，要垒成方柱体。
经过长期观察，atm 发现了稳定骰子的奥秘：有些数字的面贴着会互相排斥！我们先来规范一下骰子：11 的对面是 44，22 的对面是 55，33 的对面是 66。假设有 mm 组互斥现象，每组中的那两个数字的面紧贴在一起，骰子就不能稳定的垒起来。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
题意：
有n个骰子要竖着排成一列，1的对面是4,2的对面是5,3的对面是6，要求有一些面之前不能互相接触，两种排列相同当且仅当每一层骰子的每个面的方向相同。问有多少种排列方法？
思路：
考虑最低一层，每个面都可以朝上，此时每个面朝上的情况都是1。考虑第二层的时候，我们假设面1 和面2不能互相接触，也就是说，前一层面1朝上和当前层面5朝上的情况不能发生，同理，前一层面2朝上跟当前层面4朝上的情况也不能发生。我们用一个数组来记录这种情况。我们可以发现，每一层的数目都只与前一层的数目有关。用dp就可以解决这个题目，但还不够快，我们可以用线性代数的知识，利用矩阵快速幂进行优化。
需要构造一个矩阵A，使得当前层=矩阵A乘上前一层。以斐波那契数列做例子
M21(两行一列){F[n],F[n-1]}=M22{1,1,1,0}*M21{F[n-1],F[n-2]}
于是可以得到M21{F[n],F[n-1]}= M22{1,1,1,0}^(n-2)* M21{F[2],F[1]},我们可以用矩阵快速幂对M22{1,1,1,0}^(n-2)进行求解。
此题也是利用类似的解法。考虑6乘6的转移矩阵a[i][j]，a[i][j]=1表示当前层以i为顶面跟前一层以j为顶面不冲突，反之则冲突。1乘6基础矩阵的b[i]表示以i为顶面的情况数，记第一层为b1，则b1[i]=1。第n层时，bn=b1[i]*a[i][j]^(n-1)。把第n层时b[i]全部加起来就得到方案数。简单验证前几次状态可知此式正确。其他细节请看代码
代码如下：
#include <stdio.h> #include <string.h> #include <algorithm> #include <iostream> #include <math.h> using namespace std; typedef long long ll; struct matrix{ int n,m; ll a[7][7]; }; matrix matrix_mul(matrix A,matrix B,int mod) { matrix C; C.n=A.n; C.m=B.m; for(int i=1;i<=A.n;i++) { for(int j=1;j<=B.m;j++) { C.a[i][j]=0; for(int k=1;k<=A.m;k++) { C.a[i][j]+=(A.a[i][k]*B.a[k][j]%mod); C.a[i][j]%=mod; } } } return C; } matrix unit() { matrix res; res.n=6; res.m=6; for(int i=1;i<=res.n;i++) { for(int j=1;j<=res.m;j++) { if(i==j) res.a[i][j]=1; else res.a[i][j]=0; } } return res; } matrix matrix_pow(matrix A,int n,int mod) { matrix res=unit(),temp=A; for(;n;n/=2) { if(n&1)res=matrix_mul(res,temp,mod); temp=matrix_mul(temp,temp,mod); } return res; } ll pow_mod(ll a,int n,int mod) { ll res=1,temp=a; for(;n;n/=2) { if(n&1)res=res*temp%mod; temp=temp*temp%mod; } return res; } int front[7]={0,4,5,6,1,2,3}; int main() { int i,j,m,x,y; ll ans=0,n; scanf("%lld%d",&n,&m); matrix col; col.n=6; col.m=6; for(i=0;i<7;i++) for(j=0;j<7;j++) col.a[i][j]=1; for(i=0;i<m;i++) { scanf("%d%d",&x,&y); col.a[front[x]][y]=0; col.a[front[y]][x]=0; } matrix res,base; for(i=1;i<=6;i++) base.a[1][i]=1; base.n=1; base.m=6; const int MOD=1e9+7; res=matrix_pow(col,n-1,MOD); res=matrix_mul(base,res,MOD); for(i=1;i<=6;i++)ans=(ans+res.a[1][i])%MOD; ans=ans*pow_mod(4,n,MOD)%MOD; printf("%lld",ans); }
