2015年Java方向C组第十题

标题：垒骰子

赌圣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

资源约定：
峰值内存消耗（含虚拟机） < 256M
CPU消耗 < 2000ms

请严格按要求输出，不要画蛇添足地打印类似：“请您输入...” 的多余内容。

所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。
注意：不要使用package语句。不要使用jdk1.7及以上版本的特性。
注意：主类的名字必须是：Main，否则按无效代码处理。

解析：

首先分析为什么2个骰子，只有一种互斥现象（1和2互斥），一共有544种垒骰子方式。

假设没有互斥现象，两颗骰子朝上的数字都有6种可能，并且两颗骰子每个数字朝上都可以旋转出4种方案，即垒骰子方式一共有：

6*6*4*4种可能性

因为有一种互斥现象，则垒骰子方式有

(6*6-2)*4*4 = 544

11.PNG

由上图可知，两个骰子方案数量为5+5+6+6+6+6=34,由于每个骰子可以旋转4个方向，34乘4乘4=544。

方案一：（递归）

static int n; //骰子数量
static int m; //互斥组合数量
static boolean[][] hc ;  //用boolean类型数组存储互斥组合(默认为false)
static int count = 0; //答案
public static void f(int layer,int up) //layer:第几层;up:朝上的数字
{
    if(layer == n){
        count ++;       
        count = count % 1000000007;
        return;
    }
    for (int i = 1; i <= 6; i++) {
        int down = 0;
        if(i == 1) down = 4;    //根据上面求下面
        if(i == 4) down = 1;
        if(i == 2) down = 5;
        if(i == 5) down = 2;
        if(i == 3) down = 6;
        if(i == 6) down = 3;
        if(hc[up][down] == true || hc[down][up] == true)
            continue;
        //每个数字朝上都可以旋转4次
        f(layer+1,i);   f(layer+1,i);   f(layer+1,i);   f(layer+1,i);
    }   
}
public static void main(String[] args) {
    Scanner input = new Scanner(System.in);
    n = input.nextInt(); //骰子数量
    m = input.nextInt(); //互斥组合数量
    hc = new boolean[7][7];
    for (int i = 0; i < m; i++) {
        int one = input.nextInt();  //互斥的第一个数字
        int two = input.nextInt();  //互斥的第二个数字
        hc[one][two] = true;
        hc[two][one] = true;
    }
    //递归调用(1,2,3,4,5,6分别朝上进行递归调用)
    for (int i = 1; i <= 6; i++) {
        f(1,i); f(1,i); f(1,i); f(1,i); //每个数字朝上都可以旋转4次
    }
    System.out.println(count);
}

递归方案，在骰子数量特别多的时候，效率低下。

方案二：（动态规划）

假设没有互斥现象，并且一个数字朝上时，不考虑旋转现象：

							总方案数量
第N层方案数量	？？	？？	？？	？？	？？	？？	？？
第三层方案数量	36	36	36	36	36	36	216
第二层方案数量	6	6	6	6	6	6	36
第一层方案数量	1	1	1	1	1	1	6
骰子点数	1朝上	2朝上	3朝上	4朝上	5朝上	6朝上

由于N的数量很大，我们可以定义一个2行的数组，将第二行内容填充为0，根据第一行累加计算得出第二行，然后将第二行内容填充到第一行，重新求第二行数据。

在求解过程中添加互斥条件的判断，最后将答案考虑旋转现象即可。

Scanner input = new Scanner(System.in);
int mod = 1000000007;
int n = input.nextInt(); //骰子数量
int m = input.nextInt(); //互斥组合数量
boolean[][] hc = new boolean[7][7]; //用boolean类型数组存储互斥组合(默认为false)
for (int i = 0; i < m; i++) {
    int one = input.nextInt();  //互斥的第一个数字
    int two = input.nextInt();  //互斥的第二个数字
    hc[one][two] = true;
    hc[two][one] = true;
}
long[][] data = new long[2][7];  //默认值0（行号从0开始，列号从1开始）
for (int i = 1; i <= 6; i++) 
    data[0][i] = 1; //将第一层所有方案数量设置成1 
//循环行（从第二行开始循环）
for (int i = 1; i < n ; i++) 
{
    for (int j = 1; j <= 6; j++) {
        data[1][j] = 0; //将第二行全部变成0
    }
    //循环6个数字，根据第一行方案数求第二行方案数
    for (int j = 1; j <= 6 ; j++) 
    {
        for (int k = 0; k <= 6; k++) 
        {
            int up = k;
            int down = 0;
            if(j == 1) down=4;
            if(j == 4) down=1;
            if(j == 2) down=5;
            if(j == 5) down=2;
            if(j == 3) down=6;
            if(j == 6) down=3;
            if(hc[up][down] == true || hc[down][up] == true)
                continue;
            data[1][j] = (data[1][j] + data[0][k]) % mod;
        }
    }
    //循环6个数字，将第二行的结果重新填充到第一行中
    for (int j = 1; j <= 6; j++) 
        data[0][j] = data[1][j];
}
long sum = 0;
//累加求data数组第二行的和
for (int i = 1; i <= 6 ; i++) {
    sum += data[1][i];
    sum = sum % mod;
}
//考虑旋转情况
for (int i = 1; i <= n; i++) {
    sum = sum * 4 % mod;
}
System.out.println(sum);

方案二相对方案一效率更高，但是也只符合60%情况。

方案三：快速幂方案

储备知识：（求2的10次方，快速幂代码如下）

long ret=1;
long i = 2;
long n = 10;
while(n!=0) {
    if( (n&1)==1) {
        ret=(ret*i);
    }
    i=(i*i);
    n>>=1;
}
System.out.println(ret);

此题目可以先写出排斥矩阵，然后求排斥矩阵的（n-1）次幂，最后考虑每个骰子旋转4次。

12.PNG
答案：

static long mod = 1000000007;
static int [] op=new int[7];

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 input = new Scanner(System.in);
    int n = input.nextInt(); //骰子数量
    int m = input.nextInt(); //互斥组合数量
    long[][] arr = new long[7][7];
    //初始化arr数组全部为1
    for (int i = 1; i <= 6; i++) {
        for (int j = 1; j <= 6; j++) {
            arr[i][j] = 1;
        }
    }
    //将排斥项设置为0
    for (int i = 1; i <= m; i++) {
        int a = input.nextInt();  //互斥的第一个数字
        int b = input.nextInt();    //互斥的第二个数字
        arr[op[a]][b] = 0;
        arr[op[b]][a] = 0;  
    }
    long[][] ans = myArrPow(arr, n-1);
    //累加矩阵元素之和
    long sum = 0;
    for (int i = 1; i < ans.length; i++) {
        for (int j = 1; j < ans[i].length; j++) {
            sum = ( sum+ans[i][j] )%mod;
        }
    }
    sum = (sum*myNumPow(4,n))%mod;
    System.out.println(sum);
}

//快速幂求i的n此幂
private static long myNumPow(long i, int n) {
    long ret=1;
    while(n!=0) {
        if( (n&1)==1) {
            ret=(ret*i)%mod;
        }
        i=(i*i)%mod;
        n>>=1;
    }
    return ret;
}

//快速幂，求数组的n次方
static long[][] myArrPow(long[][] arr,int n)
{
    //此数组和任何数组相乘结果还是当前数组
    long[][] ans = new long[7][7];
    for (int i = 1; i <= 6; i++)
        ans[i][i] = 1;
    while(n!=0) {
        if((n&1)==1) {
            ans=mul(ans,arr);
        }
        arr=mul(arr,arr);
        //n右移一位 除以2
        n>>=1;
    }
    return ans; 
}

//数组乘法，C[i][j]为A的第i行与B的第j列对应乘积的和
private static long[][] mul(long[][] a, long[][] b) {
    long [][] ans=new long[7][7];
    for(int i=1;i<=6;i++) {
        for (int j = 1; j <= 6; j++) {
            for (int k = 1; k <= 6; k++) {
                ans[i][j]=( ans[i][j]+a[i][k]*b[k][j] )%mod;
            }
        }
    }
    return ans;
}