垒骰子(2015-Java-B-09)

题目描述

赌圣atm晚年迷恋上了垒骰子，就是把骰子一个垒在另一个上边，不能歪歪扭扭，要垒成方柱体。
经过长期观察，atm 发现了稳定骰子的奥秘：有些数字的面贴着会互相排斥！
我们先来规范一下骰子：1的对面是 4，2的对面是 5，3的对面是6。
假设有 m组互斥现象，每组中的那两个数字的面紧贴在一起，骰子就不能稳定的垒起来。
atm想计算一下有多少种不同的可能的垒骰子方式。
两种垒骰子方式相同，当且仅当这两种方式中对应高度的骰子的对应数字的朝向都相同。
由于方案数可能过多，请输出模 1e9+7的结果。
不要小看了 atm 的骰子数量哦～

考点

dp+快速幂+矩阵快速幂+矩阵乘法（涉及线性代数）

参考文献

蓝桥杯郑未老师视频讲解

抽象化模板

快速幂

  private static long power(long i,int n){
        long ans = 1;
        while(n!=0){
            if((n&1)==1){
                ans = (ans*i)%MOD;
            }
            i = (i*i)%MOD;
            n>>=1;
        }

        return ans;
    }

矩阵快速幂

private static long[][] mPow(long[][] conflict, int n){
        //单位矩阵，主对角线为1其余为0
        long[][] e = new long[6][6];
        for(int i = 0; i < 6; i++){
            for(int j = 0; j < 6; j++){
                if(i == j){
                    e[i][j] = 1;
                }else {
                    e[i][j] = 0;
                }
            }
        }

        while(n!=0){
            if((n&1)==1){
                e = mMul(e,conflict);
            }
            conflict = mMul(conflict,conflict);
            n>>=1;
        }

        return e;
    }

矩阵乘法

 private static long[][] mMul(long[][] a, long[][]b){
        long[][] ans = new long[6][6];
        for(int i = 0; i < 6; i++){
            for(int j = 0; j < 6; j++){
                for(int k = 0; k < 6; k++){
                    ans[i][j] = (ans[i][j]+a[i][k]*b[k][j])%MOD;
                }
            }
        }

        return ans;
    }

Java代码

import java.util.*;
public class Main{
    private static int n,m;
    private static final long MOD = 1000000007;
    private static int[] op = new int[7];

    private static void init(){
        op[1] = 4;
        op[2] = 5;
        op[3] = 6;
        op[4] = 1;
        op[5] = 2;
        op[6] = 3;
    }

    public static void main(String[] args){
        init();
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();

        long conflict[][] = new long[6][6];
        for(int i = 0; i < 6; i++){
            for(int j = 0; j < 6; j++){
                conflict[i][j]=1;
            }
        }
        //建立冲突矩阵
        for(int i = 0; i < m; i++){
            int a = sc.nextInt();
            int b = sc.nextInt();
            conflict[op[a]-1][b-1]=0;
            conflict[op[b]-1][a-1]=0;
        }
        //求冲突矩阵的n-1次方
        long[][] mPow_n_1 = mPow(conflict,n-1);
        //累加矩阵的每个元素
        long res = 0;
        for(int i = 0; i < 6; i++){
            for(int j = 0; j < 6; j++){
                res = (res + mPow_n_1[i][j])%MOD;
            }
        }
        //res*4的n次方
        System.out.println(res*power(4,n)%MOD);
    }

    private static long power(long i,int n){
        long ans = 1;
        while(n!=0){
            if((n&1)==1){
                ans = (ans*i)%MOD;
            }
            i = (i*i)%MOD;
            n>>=1;
        }

        return ans;
    }
    /**
    *矩阵的快速幂
    */
    private static long[][] mPow(long[][] conflict, int n){
        long[][] e = new long[6][6];
        for(int i = 0; i < 6; i++){
            for(int j = 0; j < 6; j++){
                if(i == j){
                    e[i][j] = 1;
                }else {
                    e[i][j] = 0;
                }
            }
        }

        while(n!=0){
            if((n&1)==1){
                e = mMul(e,conflict);
            }
            conflict = mMul(conflict,conflict);
            n>>=1;
        }

        return e;
    }
    /**
    *矩阵相乘
    */
    private static long[][] mMul(long[][] a, long[][]b){
        long[][] ans = new long[6][6];
        for(int i = 0; i < 6; i++){
            for(int j = 0; j < 6; j++){
                for(int k = 0; k < 6; k++){
                    ans[i][j] = (ans[i][j]+a[i][k]*b[k][j])%MOD;
                }
            }
        }

        return ans;
    }

}