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

Meickol · 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;
}

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

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