蓝桥杯 垒骰子 （DP+矩阵快速幂）

赌圣atm晚年迷恋上了垒骰子，就是把骰子一个垒在另一个上边，不能歪歪扭扭，要垒成方柱体。

经过长期观察，atm 发现了稳定骰子的奥秘：有些数字的面贴着会互相排斥！

我们先来规范一下骰子：1 的对面是 4，2 的对面是 5，3 的对面是 6。

假设有 m 组互斥现象，每组中的那两个数字的面紧贴在一起，骰子就不能稳定的垒起来。

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

思路

dp[i][j] 代表高度为i，顶面点数为j的方案数，于是 dp[i][j] 就等于i-1高度时所有与j对面无冲突方案数的累加。

当然，最下面一层所有面在上的方案数都为1，求得结果后还要乘以 4^i ，因为每一个骰子都可以保证顶端点数不变的情况下四面旋转。

不过对于这道题1e9的数据O(n)的算法感觉还是会超时

于是使用了矩阵的方式来计算，关于矩阵列向量的选择求和与斐波那契数列相似。

构造出这样一个冲突矩阵之后便可以用矩阵快速幂的方法很快解决了，最终再与初始第一层的方案数相乘，便是结果。

只是因为网上找不到评测平台，所以代码的正确与否无法保证，不过思路就是这样啦！

普通o(n)解法

#include<iostream>
#include<algorithm>
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<iostream>
using namespace std;
#include<queue>
#include<stack>

#define mod 1000000007
typedef __int64 LL;

bool isc[7][7]; //存储冲突面

LL mult(LL a,LL n)  //数的快速幂 a^n
{
    LL ans=1;
    while(n)
    {
        if(n&1)ans=(ans*a)%mod;
        a=(a*a)%mod;
        n>>=1;
    }
    return ans;
}

int main()
{
    LL n,m;
    while(~scanf("%I64d%I64d",&n,&m))
    {
        memset(isc,false,sizeof(isc));
        for(int i=0; i<m; i++)
        {
            int a,b;
            scanf("%d%d",&a,&b);
            isc[a][b]=isc[b][a]=true;
        }
        LL dp[2][7],e=0;    //利用滚动数组的原理，不浪费多余空间
        for(int i=1; i<7; i++)  //初始化第0层
            dp[0][i]=1;
        for(LL i=1; i<n; i++)   //剩余n-1层
        {
            e^=1;
            for(int j=1; j<7; j++)  //上面一层下面为j
            {
                dp[e][j]=0;
                for(int k=1; k<7; k++)  //下面一层顶端为k
                    if(!isc[j][k])      //不冲突
                        dp[e][j]+=dp[e^1][k];
                dp[e][j]%=mod;      //取模
            }
        }
        LL sum=0;
        for(int i=1; i<7; i++)  //求最后一层的所有情况和
            sum+=dp[e][i];
        printf("%I64d\n",(sum*mult(4,n))%mod);  //每个都可以四面旋转
    }
    return 0;
}

矩阵解法

#include<iostream>
#include<algorithm>
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<iostream>
using namespace std;
#include<queue>
#include<stack>

#define mod 1000000007
typedef __int64 LL;

struct marx     //定义矩阵
{
    int d[6][6];
    marx() {}
    marx(int x) //构造：对角线赋值为x
    {
        memset(d,0,sizeof(d));
        for(int i=0; i<6; i++)
            d[i][i]=x;
    }
};

marx mul(marx a,marx b) //矩阵乘法
{
    marx res=marx(0);   //零
    for(int i=0; i<6; i++)
        for(int j=0; j<6; j++)
            for(int s=0; s<6; s++)
                res.d[i][j]=((a.d[i][j]*b.d[j][s])%mod+res.d[i][j])%mod;
    return res;
}

LL sb;
marx mult(marx t,LL n)  //矩阵快速幂 t^n
{
    marx res=marx(1);   //单位矩阵
    LL ans=1,ss=4*4;    //顺便计算了一下 4^n
    while(n)
    {
        if(n&1)res=mul(res,t),ans=(ans*ss)%mod;
        t=mul(t,t);
        ss=(ss*ss)%mod;
        n>>=1;
    }
    sb=ans;
    return res;
}

int main()
{
    LL n,m;
    while(~scanf("%I64d%I64d",&n,&m))
    {
        marx isc,ans;
        for(int i=0; i<6; i++)
        {
            for(int j=0; j<6; j++)
                isc.d[i][j]=1;  //初始化矩阵
            ans.d[1][i]=1;  //第一层各面情况
        }
        int a,b;
        for(int i=0; i<m; i++)
        {
            scanf("%d%d",&a,&b);
            isc.d[a-1][b-1]=isc.d[b-1][a-1]=0;  //标记互斥面
        }
        LL sum=0;
        ans=mul(ans,mult(isc,n-1)); //计算矩阵幂以及与第一层结果的乘积
        for(int i=0; i<6; i++)
            sum=(sum+ans.d[1][i])%mod;  //最终求和
        printf("%I64d\n",(sb*sum)%mod); //每一层可以四面旋转
    }
    return 0;
}