自动搬运

查看原文

来自洛谷，原作者为

	Meickol **

搬运于2025-08-24 22:40:49，当前版本为作者最后更新于2024-01-23 11:30:12，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

思路分析：

一、思考整体思路及状态表示式，以便后续根据递推关系建立状态转移方程。

​ $f[i][j]$ 表示自上往下第 $i$ 个骰子且该骰子朝上的一面为数字 $j$ 的所有可能性。

​ 又因为每个骰子侧面可以旋转，即每个骰子可能性 $\times$ $4$

​ 因而当不考虑互斥情况时，状态转移方程应为 $f[i][j]=\sum_{k=1}^{6} f[i-1][k]\times4$。

​ 同时最终答案应为 $ans=\sum_{k=1}^{6} f[n][k]$。

二、考虑互斥情况以及 $oppo$ 的处理方式。

​ 但这题需要考虑互斥情况，接下来考虑互斥的处理。

​ 利用 $st$ 数组记录互斥信息，输入 $a,b$ 后将 $st[a][b]$ 进行标记表示 $a$ 和 $b$ 间存在互斥关系。

​ 因为是考虑紧挨之间是否存在互斥关系。

​ 如考虑第 $i$ 个骰子与第 $i-1$ 个骰子之间是否存在互斥情况，即第 $i$ 个骰子底部与第 $i-1$ 个骰子顶部数字是否互斥。

​ 因而引入 $oppo[j]$ 表示一个以数字 $j$ 朝上的骰子中在数字 $j$ 对面的数字。

​ 不考虑互斥情况时状态转移方程：$f[i][j]=\sum_{k=1}^{6} f[i-1][k] \times 4$

​ 考虑互斥情况后状态转移方程：$f[i][j]=\sum_{k=1}^{6} f[i-1][k] \times 4 \times st[k][oppo[j]]$

​ 通过图像理解也很直观：

​

​ 另外对于 $oppo$ 的处理有两种方式，其中我们采用了第一种方式

​ Ⅰ、数组保存：利用 $oppo$ 数组来保存骰子数字的对立面数字。

int oppo[7]={0,4,5,6,1,2,3};

​ Ⅱ、函数计算：

int get_oppo(int x){
	if(x>3) return x-3;
	else return x+3;
}

三、进一步思考

​ 对于答案，$ans=F_n,F_n=f[n][1]+f[n][2]+f[n][3]+f[n][4]+f[n][5]+f[n][6]$

​ 即 $ans=\sum_{k=1}^{6} f[n][k]$

​ 以及每一个 $f[i][j]$ 的计算：$f[i][j]=\sum_{k=1}^{6}f[i-1][k] \times 4 \times st[k][oppo[j]]$

​ 转化成伪代码：

for(int i=1;i<=6;i++) f[1][i]=4;
for(int i=2;i<=n;i++)
    for(int j=1;j<=6;j++)
        if(非互斥) f[i][j] = (f[i][j] + f[i - 1][j] * 4)

​ 易知时间复杂度为 $O(n)$

​ 考虑到数据范围：$1≤n≤10^9$，以及题目所给的 $1s$ 时间上限。

​ 显然会超时，需要进行优化！

四、矩阵加速（矩阵快速幂）

​ 考虑到数据范围：$1≤n≤10^9$，于是想到利用矩阵乘法进行优化以降低时间复杂度。

​ 使用矩阵快速幂的方式，复杂度 $O(\log n)$，可以解决问题。

​

$$例:当存在\begin{bmatrix} 1&2 \\ 1&5 \\ 2&6 \\ 3&4 \\ 5&5 \end{bmatrix}的互斥关系时, F(n) \ \begin{bmatrix} 4& 0& 4& 4& 0& 4\\ 4& 4& 0& 0& 4& 4\\ 0& 4& 4& 4& 4& 4\\ 4& 4& 4& 4& 4& 4\\ 4& 0& 4& 0& 4& 4\\ 4& 4& 4& 4& 0& 4 \end{bmatrix} =F(n+1) $$

​ 观察可发现，$F_n=F_1 \times A^{n-1}$

​ 将 $res$ 矩阵的值初始化为 $F_1$

for(int i=1;i<=6;i++)res.c[1][i]=4;

​ 对于常数矩阵 $A$ 的设置：

for(int i=1;i<=6;i++){
    for(int j=1;j<=6;j++){
        if(st[i][oppo[j]]) A.c[i][j]=0;
        else A.c[i][j]=4;
    }
}

最终代码：

#include<bits/stdc++.h>
using namespace std;
#define rep(x,y,z) for(int x=y;x<=z;x++)
typedef long long LL;
const int mod=1e9+7;
int n,m,a,b,oppo[7]={0,4,5,6,1,2,3};
bool st[7][7];
struct matrix{
    LL c[7][7];
    matrix(){memset(c,0,sizeof c);}
}A,res;
matrix operator * (matrix &x,matrix &y){
    matrix t;
    rep(i,1,6){
        rep(j,1,6){
            rep(k,1,6){
                t.c[i][j]=(t.c[i][j]+x.c[i][k]*y.c[k][j])%mod;
            }
        }
    }
    return t;
}
void fastpow(LL k){
    rep(i,1,6) res.c[1][i]=4;
    rep(i,1,6){
        rep(j,1,6){
            if(st[i][oppo[j]]) A.c[i][j]=0;
            else A.c[i][j]=4;
        }
    }
    while(k){
        if(k&1) res=res*A;
        A=A*A;
        k>>=1;
    }
}
int main(){
    cin>>n>>m;
    while(m--){
        cin>>a>>b;
        st[a][b]=st[b][a]=1;
    }
    fastpow(n-1);
    LL ans=0;
    rep(i,1,6) ans=(ans%mod+res.c[1][i]%mod)%mod;
    cout<<ans;
    return 0;
}