壘骰子
賭圣atm晚年迷戀上了壘骰子，就是把骰子一個壘在另一個上邊何吝，不能歪歪扭扭溉委，要壘成方柱體鹃唯。
經過長期觀察爱榕，atm 發(fā)現了穩(wěn)定骰子的奧秘：有些數字的面貼著會互相排斥！
我們先來規(guī)范一下骰子：1 的對面是 4坡慌，2 的對面是 5黔酥，3 的對面是 6。
假設有 m 組互斥現象洪橘，每組中的那兩個數字的面緊貼在一起跪者，骰子就不能穩(wěn)定的壘起來。
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
解題思路
首先搀捷，這題有很多的解題方式，但這里主要使用矩陣快速冪來解決多望，如果對矩陣快速冪不是很熟悉的玩家菊匿，呸锅纺，讀者。。請看一下前面的兩篇文章矩陣快速冪入門和矩陣快速冪進階
看到這道題目潮瓶，第一感覺是，這題怎么能用矩陣快速冪做车吹？遞推式都沒給当辐，怎么求轉移矩陣呢黎棠？
首先我們理解一下題目
我們先看一下只有一組互斥現象1-2，且n=1镰绎、n=2脓斩、n=3的情況，也就是以下三組測試數據
#測試數據一 #測試數據二 #測試數據三
1 1 2 1 3 1
1 2 1 2 1 2
- 第一個測試數據（先不考慮側面的旋轉）
| 情況 | 點1朝上 | 點2朝上 | 點3朝上 | 點4朝上 | 點5朝上 | 點6朝上 |
|---|---|---|---|---|---|---|
| 第一層 | 1 | 1 | 1 | 1 | 1 | 1 |
總數 = (1+1+1+1+1+1) × 41 = 24 （側面每種情況都能進行4種旋轉）
- 第二個測試數據（先不考慮側面的旋轉）
| 情況 | 點1朝上 | 點2朝上 | 點3朝上 | 點4朝上 | 點5朝上 | 點6朝上 |
|---|---|---|---|---|---|---|
| 第一層 | 1 | 1 | 1 | 1 | 1 | 1 |
| 第二層 | 6 | 6 | 6 | 5 | 5 | 6 |
總數 = (6+6+6+5+5+6) × 42 = 544 （側面每種情況都能進行4種旋轉）
- 第三個測試數據（先不考慮側面的旋轉）
| 情況 | 點1朝上 | 點2朝上 | 點3朝上 | 點4朝上 | 點5朝上 | 點6朝上 |
|---|---|---|---|---|---|---|
| 第一層 | 1 | 1 | 1 | 1 | 1 | 1 |
| 第二層 | 6 | 6 | 6 | 5 | 5 | 6 |
| 第三層 | 34 | 34 | 34 | 28 | 28 | 34 |
首先畴栖，解釋一下上述表格的意思随静，比如第二層，點1朝上對應是6意思是：當只有兩層的時候吗讶，第二層（最上面的一層）頂面的點數是1的情況燎猛，一共有6種。
為什么是6照皆？點1朝上重绷，也就說明點4朝下，因為沒有和4沖突的膜毁，所以第一層怎么放都可以昭卓，一共6種（也就是第一層的6種情況相加）
那第二層，點4朝上的時候為什么對應的是5呢瘟滨？點4朝上候醒，也就說明點1朝下，因為1-2是互斥現象杂瘸，所以第一層中點2朝上的情況就不能加上了倒淫，所以一共5種。
現在到了第三層败玉。第三層敌土，點1朝上的情況一共有34種（再重復一遍，第三層點1朝上的情況绒怨，是指最上面那個骰子點1朝上纯赎，然后下面兩個骰子可以存在的所有情況）。為什么是34南蹂？因為點1朝上犬金，也就是說點4朝下，和任何數字都不沖突六剥，所以是第二層的所有情況相加（是不是感覺進DP的坑了）
然后看下第三層晚顷，點4朝上的情況，點4朝上也就說明點1朝下疗疟，因為1-2是互斥現象该默，所以第三層中點4朝上的情況 = 第二層中點1+點3+點4+點5+點6朝上的情況的總和
這真的不是DP嗎？和矩陣快速冪有啥關系
乘號右邊栓袖，從上到下分別是
點1朝上匣摘、點2朝上……的情況，從左到右分別是第一層裹刮、第二層音榜、第三層的情況。
那是怎么得到這個轉移矩陣的呢捧弃？赠叼？再回上去看下，剛才遞推出來的各層的情況违霞，除了和DP類似嘴办，是不是也和一個遞推公式很類似呢？
dp[i][j] = ∑ dp[i-1][j] (1<=j<=6)
其中dp[i][j]表示第i層买鸽，點j朝上的情況
如果僅僅是單純的前一層的各個情況相加涧郊，我們的轉移矩陣可以是這樣的
但是我們還有一步，需要把互斥現象組去掉癞谒。那怎么去呢底燎？把該點置0刃榨？對５狻！比如互斥組1-2枢希，當點4朝上時桌吃，點1就朝下，這時苞轿，子層不能加上點2朝上的情況茅诱，所以需要把A[4][2]置0。當點5朝上時搬卒，點2就朝下瑟俭，子層不能加上點1朝上的情況，所以需要把A[5][1]置0
這里的A[5][1]表示第5行第1列契邀，在真正意義上的數組計算時摆寄，使用的是A[4][0]
for(int i=0; i<m; i++){
cin>>a>>b;
temp[dp[a]-1][b-1] = temp[dp[b]-1][a-1] = 0;
}
上述代碼中，比如輸入互斥現象1 3坯门。因為點1對面是點5微饥。所以當點5朝上時，點1朝下古戴，子層不能出現點3朝上的情況欠橘。同理點3對面是點6，所以當點6朝上時现恼，點3朝下肃续，子層中不能出現點1朝上的情況黍檩。因為數組從0開始，所以有temp[dp[a]-1][b-1] = temp[dp[b]-1][a-1] = 0;
不過最后還需要注意一點始锚！4n不要忘了建炫，因為側面的情況開始就沒考慮。但是每一層的側面有4種情況疼蛾，所以第n層的總情況只要將上述結果乘以4n就可以了肛跌。
完整代碼
#include <iostream>
#include <string.h>
using namespace std;
const long long int N = 1000000007;
void Matrix(long long int (&a)[6][6],long long int b[6][6]){
long long int tmp[6][6] = {0};
for(int i = 0; i < 6; ++i)
for(int j = 0; j < 6; ++j)
for(int k = 0; k < 6; ++k)
tmp[i][j] = (tmp[i][j] + a[i][k] * b[k][j]) % N;
for(int i = 0; i < 6; ++i)
for(int j = 0; j < 6; ++j)
a[i][j] = tmp[i][j];
}
int main(int argc, const char * argv[]) {
long long int n,m,a,b,sum = 0,p = 4,temp[6][6],cot[6][6] = {0},dp[7] = {0,4,5,6,1,2,3};
cot[0][0] = cot[1][1] = cot[2][2] = cot[3][3] = cot[4][4] = cot[5][5] = 1;
fill(temp[0],temp[0]+36,1); //初始化為1
cin>>n>>m;
for(int i=0; i<m; i++){
cin>>a>>b;
temp[dp[a]-1][b-1] = temp[dp[b]-1][a-1] = 0; //互斥位置0
}
m = n - 1;
while(m){ //計算矩陣快速冪
if(m & 1) Matrix(cot,temp);
Matrix(temp,temp);
m /= 2;
}
for(int i=0; i<6; i++)
for(int j=0; j<6; j++)
sum = (sum + cot[i][j])%N; //結果集之和
while(n){ //同快速冪求解4^n
if(n&1) sum = (sum*p)%N; //注意一開始是sum開始乘的
p = (p*p)%N;
n /= 2;
}
cout<<sum<<endl;
return 0;
}
由于找不到提交代碼的地方，所以這不算是已經AC的代碼察郁，不過試了一些數據衍慎，和標程的輸出都一樣
