壘骰子

賭圣atm晚年迷戀上了壘骰子，就是把骰子一個(gè)壘在另一個(gè)上邊，不能歪歪扭扭，要壘成方柱體。
經(jīng)過長(zhǎng)期觀察，atm 發(fā)現(xiàn)了穩(wěn)定骰子的奧秘：有些數(shù)字的面貼著會(huì)互相排斥！
我們先來規(guī)范一下骰子：1 的對(duì)面是 4，2 的對(duì)面是 5，3 的對(duì)面是 6。
假設(shè)有 m 組互斥現(xiàn)象，每組中的那兩個(gè)數(shù)字的面緊貼在一起，骰子就不能穩(wěn)定的壘起來。 atm想計(jì)算一下有多少種不同的可能的壘骰子方式。
兩種壘骰子方式相同，當(dāng)且僅當(dāng)這兩種方式中對(duì)應(yīng)高度的骰子的對(duì)應(yīng)數(shù)字的朝向都相同。
由于方案數(shù)可能過多，請(qǐng)輸出模 10^9 + 7 的結(jié)果。
不要小看了 atm 的骰子數(shù)量哦～

「輸入格式」
第一行兩個(gè)整數(shù) n m
n表示骰子數(shù)目
接下來 m 行，每行兩個(gè)整數(shù) a b ，表示 a 和 b 不能緊貼在一起。
「輸出格式」
一行一個(gè)數(shù)，表示答案模 10^9 + 7 的結(jié)果。

「樣例輸入」
2 1
1 2
「樣例輸出」
544

「數(shù)據(jù)范圍」
對(duì)于 30% 的數(shù)據(jù)：n <= 5
對(duì)于 60% 的數(shù)據(jù)：n <= 100
對(duì)于 100% 的數(shù)據(jù)：0 < n <= 10^9, m <= 36

資源約定：
峰值內(nèi)存消耗（含虛擬機(jī)） < 256M
CPU消耗? < 2000ms

請(qǐng)嚴(yán)格按要求輸出，不要畫蛇添足地打印類似：“請(qǐng)您輸入...” 的多余內(nèi)容。
所有代碼放在同一個(gè)源文件中，調(diào)試通過后，拷貝提交該源碼。
注意：不要使用package語句。不要使用jdk1.7及以上版本的特性。

注意：主類的名字必須是：Main，否則按無效代碼處理。

解析：首先分析一下樣例輸出中544怎么來的，題意中指出不同的朝向是不同的結(jié)果。所有對(duì)于n個(gè)骰子來說，最終結(jié)果就需要再乘上4^n，而樣例中兩個(gè)骰子就是4^2，544/(4^2) = 34，而34代表骰子接觸的兩個(gè)面的情況，5+5+6+6+6+6=34。

下面的代碼用到了矩陣快速冪

import java.util.Scanner;public class Main {static final double MOD = 10e9-7;static int[][] arr = new int[6][6];public static void main(String[] args) {Scanner input = new Scanner(System.in);int n = input.nextInt();int m = input.nextInt();/*** 初始化arr數(shù)組* */for (int i = 0; i < 6; i++) {for (int j = 0; j < 6; j++) {arr[i][j] = 1;}}for (int i = 0; i < m; i++) {int a = input.nextInt();int b = input.nextInt();arr[a-1][b-1] = 0;arr[b-1][a-1] = 0;}int[][] ans = pow(arr, n-1);int sum = 0;for (int i = 0; i < 6; i++) {for (int j = 0; j < 6; j++) {sum += ans[i][j]%MOD;}}/*** 旋轉(zhuǎn)情況 4^n* */sum *= Math.pow(4, n)%MOD;System.out.println((int)(sum%MOD));}private static int[][] pow(int[][] arr, int k) {/*** 初始化單位矩陣* */int[][] ans = new int[6][6];for (int i = 0; i < 6; i++) {ans[i][i] = 1;}/*** 矩陣快速冪核心算法* */while (k != 0) {if (k % 2 != 0) {ans = Multiply(arr, ans);} else {arr = Multiply(arr, arr);}k >>= 1;}return ans;}private static int[][] Multiply(int[][] m, int[][] n) { // 標(biāo)準(zhǔn)計(jì)算矩陣乘法算法int rows = m.length;int cols = n[0].length;int[][] r = new int[rows][cols];for (int i = 0; i < rows; i++) {for (int j = 0; j < cols; j++) {for (int k = 0; k < m[i].length; k++) {r[i][j] += (m[i][k] * n[k][j])%MOD;}}}return r;} }

?

?

?

總結(jié)

以上是生活随笔為你收集整理的蓝桥杯第六届省赛JAVA真题----垒骰子的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。