[藍橋杯][2015年第六屆真題]壘骰子(只是給自己複習用）

[藍橋杯][2015年第六屆真題]壘骰子

題目描述：

賭聖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
請嚴格按要求輸出，不要畫蛇添足地列印類似：「請您輸入…」的多餘內容。
所有程式碼放在同一個原始檔中，偵錯通過後，拷貝提交該原始碼。
注意: main函數需要返回0
注意: 只使用ANSI C/ANSI C++ 標準，不要呼叫依賴於編譯環境或操作系統的特殊函數。注意: 所有依賴的函數必須明確地在原始檔中 #include ，不能通過工程設定而省略常用標頭檔案。
提交時，注意選擇所期望的編譯器型別。

思路：應該馬上能想到用暴力解法，也就是深收、遞回的做法。雖然明顯會超時。。。應該有30%的分值

做法也非常簡單，就是總數會等於最上面的數目（分別六種朝上的面）即6來乘以剩下的n-1顆骰子的情況。。。。
然後一直遞回下去。。。

細心的朋友已經發現了，你不用轉動嗎？
所以我們最後的結果會乘以4ⁿ

不要忘記%MOD

#include<iostream>
using namespace std;
int op[7];
bool conflict[7][7];
const int MOD=100000007;
//define MOD 1000000007 

void init(){
	op[1]=4;
	op[4]=1;
	op[2]=5;
	op[5]=2;
	op[3]=6;
	op[6]=3;
}
int f(int up,int cnt){//up代表上一顆骰子的朝向，cut代表剩下的骰子數目 
	//出口
	if(cnt==0) return 1; //這裏代表上一層朝上的是up，但是這一層我們沒有骰子了
						//所以上一層朝上是up的數目是4*1 
	
	long long ant=0;
	for(int upp=1;upp<=6;upp++){
		if(conflict[op[up]][upp]==true) continue;
		ant=(ant+4*f(upp,cnt-1))%MOD;
	}
	return ant;
}
int main(){
	int n,m;
	cin>>n>>m;
	init();
	
	for(int i=1;i<=m;i++){
		int x,y;
		cin>>x>>y;
		conflict[x][y]=true;
		conflict[y][x]=true;
		
	}
	long long ans=0;
	for(int up=1;up<=6;up++){
		ans=((ans+4*f(up,n-1))%MOD);
	} 
	cout<<ans;
	
	return 0;
}

思路二：動態規劃

剛纔是從上往下來算，這次我們最下面下麪一個骰子開始（其實都一樣，我只是定義一個正反向，方便在計算骰子的「對面」時不搞混）

雖然還是不能拿滿分，但是可以拿70%的分值

本質就是定義一個卷動陣列來記錄「兩層」值，0層是上一次放好的每面向上的個數，1層用來更新數據，給下次用。

程式碼及解釋如下：

#include<iostream>
using namespace std;
int op[7];
long long dp[2][7];//卷動使用 
bool conflict[7][7];
const int MOD=100000007;
//define MOD 1000000007 

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

int main(){
	int n,m;
	cin>>n>>m;
	init();
	
	for(int i=1;i<=m;i++){
		int x,y;
		cin>>x>>y;
		conflict[x][y]=true;
		conflict[y][x]=true;
		
	}
	//以上輸入已完成
	
	//初始化dp 
	for(int j=1;j<=6;j++){
		dp[0][j] = 1;
	} 
	
	int cur = 0;//用來使dp卷動 
	
	for(int level=2;level<=n; ++level){
		cur = 1-cur;
	//嘗試將6個面放在當前這一層的朝上方向
	 	for(int j=1;j<=6;++j){
	 		dp[cur][j] = 0;//初始化以便下面 下麪更新
		//將與op[j]不衝突的上一次層格子裏面的數目累加起來
			for(int i=1;i<=6;++i){
				if(conflict[op[j]][i]) continue;//i代表上一次格子的i朝上的累加總數
				dp[cur][j] = (dp[cur][j]+dp[1-cur][i]) % MOD;
			}	  
		 }
	} 
	long long sum=0;
	for(int k=1;k<=6;++k){
		sum = (sum+dp[cur][k])%MOD;	
	}
	
	//快速冪運算
	//求4的n次冪
	//將2^22轉化爲 2^16 * 2^0 * 2^4 * 2^1 * 2^0
	//22的二進制10110 
	long long ans = 1;
	long long tem = 4;
	long long p = n;
	
	while(p!=0){
		//位與運算，先將n和1轉化爲4*8個bit的二進制，如何1代表trueo
		//0代表false，然後就是正常的與運算了 
		if(p & 1==1) ans=(ans*tem)%MOD;
		tem=(tem*tem)%MOD;
		p >>= 1; //p=p/2; 有符號右移運算 p=p/2^1
				 //本質上是轉化爲2進位制二補數然後右移，符號位補齊 
	}
	 
	cout<<(sum*ans)%MOD;
	
	return 0;
}

思路三：說難想到的話其實也還好，當你在做動態規劃的時候就會有這麼點感覺，好像每次都是乘以一樣的東西，然後我們把這東西定義爲矩陣就行啦

但是問題是如果比賽已經將動態規劃寫好，還有時間改嗎

程式碼及註釋：

//跟動態規劃一樣，先放最下面 下麪一層
//衝突矩陣a[i][j]代表i+1向上時會不會與下面 下麪的j+1衝突 
#include<iostream>
//#include<bits/stdc++.h>
#include<map>
#include<vector>

using namespace std;
typedef long long LL;

int n,m;
map <int,int> op;
 
const int MOD=1000000007;
//define MOD 1000000007 

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

//定義全1矩陣 
struct M{
	LL a[6][6];
	M(){
		for(int i=0;i<6;i++){
			for(int j=0;j<6;j++){
				
				a[i][j]=1;
			}
		}
	}
};
//矩陣乘法 
M mMultiply(M m1,M m2){
	M ans;
	for(int i=0;i<6;i++){
		for(int j=0;j<6;j++){
			ans.a[i][j]=0;
			for(int k=0;k<6;k++){
				ans.a[i][j]=(ans.a[i][j]+m1.a[i][k]*m2.a[k][j])%MOD;
			}
		}
	}
	return ans; 
}
//矩陣M的k次冪
M mPow(M m,int k){
	M ans;
//初始化ans爲單位矩陣
	for(int i=0;i<6;i++){
		for(int j=0;j<6;j++){
			if(i==j) 
				ans.a[i][j]=1;
			else
				ans.a[i][j]=0;
		} 
	}
	
	while(k!=0){
		if((k & 1)==1) {
			ans = mMultiply(ans,m);
		}
		m = mMultiply(m,m);
		k >>= 1;
	}
	return ans;
 
}

//快速冪運算
//求4的n次冪
//將2^22轉化爲 2^16 * 2^0 * 2^4 * 2^1 * 2^0
//22的二進
LL TM(LL tem,LL n){
	long long ans = 1;
	//long long tem = 4;
	long long p = n;
	
	while(p!=0){
		//位與運算，先將n和1轉化爲4*8個bit的二進制，如何1代表trueo
		//0代表false，然後就是正常的與運算了 
		if(p & 1==1) ans=(ans*tem)%MOD;
		tem=(tem*tem)%MOD;
		p >>= 1; //p=p/2; 有符號右移運算 p=p/2^1
				 //本質上是轉化爲2進位制二補數然後右移，符號位補齊 
	}
	return ans;	
}
	

int main(){
	init();
	cin>>n>>m;
	M cMatrix;//衝突矩陣
	for(int i=1;i<=m;i++){
		int a,b;
		cin>>a>>b;
		//衝突矩陣a[i][j]代表i+1向上時會不會與下面 下麪的j+1衝突
		cMatrix.a[op[a]-1][b-1]=0;
		cMatrix.a[op[b]-1][a-1]=0;
	}
	
	M cM_n_1 = mPow(cMatrix,n-1);
	LL ans=0;
	
	for(int j=0;j<6;j++){
		for(int i=0;i<6;i++){
			ans=(ans+cM_n_1.a[j][i])%MOD;
		}
	}
	
	LL a =  TM(4,n);
	cout<<(ans*a)%MOD;
	return 0;	
	}

本題要掌握的有

快速冪
矩陣定義，及矩陣乘法
矩陣快速冪
當出現這種」樹狀「，考慮動態規劃及矩陣冪

[藍橋杯][2015年第六屆真題]壘骰子(只是給自己複習用）