题解：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}\times4\times to_{opp_j,k}\)。
此时已经接近正解了，但转移复杂度为 \(O(36n)\)，无法接受，于是考虑使用矩阵加速。
由于转移过程与 \(i\) 无关，所以考虑矩阵加速转移，记 \(mp_{i,j}\) 为上一个骰子 \(i\) 点数朝上，当前骰子 \(j\) 点数朝上的方案数，这样就可以以 \(O(6^3logn)\) 的复杂度通过本题。
接下来是参考代码。
[code]#include#define int long longusing 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>m;         while(m--){                int u,v;                 cin>>u>>v;                 to[v]=1,to[v]=1;//这里的to数组为了方便，与上述的标记意义相反，1为舍去        }        qpow(n-1);         int res=0;         for(int i=1;i