题解：Luogu-P8624 [蓝桥杯 2015 省 AB] 垒骰子

复习了一遍矩阵快速幂，感谢 @naroto2022 的讲课和分享的好题。

本题是一道动态规划结合矩阵加速的好题。

读完题考虑设计状态，记 (f_{i,j}) 为第 (i) 个骰子点数 (j) 朝上时的方案数，则初步得出转移方程为 (f_{i,j} = sum_{k = 1}^{6}f_{i-1,k}times 4)（乘上 (4) 是因为侧面翻转有 (4) 种情况）。

接下来对题目中给出的约束条件进行思考，不妨标记一个二维数组 (to) 来保存每个限制。当 (to_{u,v}) 为 (0) 时，方案舍去；否则就维持原状。再标记一个 (opp) 数组，标记每个点数的对面点数。于是得出进一步的转移方程为 (f_{i,j}=sum_{k=1}^{6}f_{i-1,k}times4times to_{opp_j,k})。

此时已经接近正解了，但转移复杂度为 (O(36n))，无法接受，于是考虑使用矩阵加速。

由于转移过程与 (i) 无关，所以考虑矩阵加速转移，记 (mp_{i,j}) 为上一个骰子 (i) 点数朝上，当前骰子 (j) 点数朝上的方案数，这样就可以以 (O(6^3logn)) 的复杂度通过本题。

接下来是参考代码。

#include<bits/stdc++.h> #define int long long using namespace std; const int M=40,N=1e9+5,P=1e9+7;  int n,m;  int opp[7]={0,4,5,6,1,2,3};  bool to[7][7];  struct JZ { 	int mp[7][7];  	JZ() { 		memset(mp,0,sizeof mp);  	} }a,ans; JZ operator*(const JZ &x,const JZ &y) { 	JZ z;  	for(int k=1;k<=6;k++){ 		for(int i=1;i<=6;i++){ 			for(int j=1;j<=6;j++){ 				z.mp[i][j]=(z.mp[i][j]+x.mp[i][k]*y.mp[k][j]%P)%P;  			} 		} 	} 	return z;  }//矩阵基本操作 void qpow(int k) { //答案矩阵预处理 	for(int i=1;i<=6;i++)ans.mp[1][i]=4; //答案矩阵第一行赋初始值4，因为第一个骰子可以放任意位置  //常数矩阵a预处理 	for(int i=1;i<=6;i++){ 		for(int j=1;j<=6;j++){ 			if(to[i][opp[j]])a.mp[i][j]=0;//不合法,舍去  			else a.mp[i][j]=4;//否则合法  		} 	} 	 	while(k){ 		if(k&1)ans=ans*a;  		a=a*a;  		k>>=1;  	}//矩阵快速幂转移计算答案 	return;  }  signed main() { 	cin.tie(0)->sync_with_stdio(0);cout.tie(0); 	cin>>n>>m;  	while(m--){ 		int u,v;  		cin>>u>>v;  		to[u][v]=1,to[v][u]=1; //这里的to数组为了方便，与上述的标记意义相反，1为舍去 	} 	qpow(n-1);  	int res=0;  	for(int i=1;i<=6;i++){   		res=(res+ans.mp[1][i]%P)%P;  	}//所得矩阵第一行元素之和即为答案 	cout<<res;  	return 0; } 

如有不足，还请指出，感谢大家观看！