藍橋杯2015C++ B組 9_壘骰子

壘骰子

賭聖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 <xxx>， 不能通過工程設定而省略常用頭檔案。

送出時，注意選擇所期望的編譯器類型。



           

這題我暫時隻想到了簡單DP算法

能從判題機騙一點分，但是幾個較大的測試點過不了

先碼住，有時間再回頭想想更好的解法

#include<iostream>
using namespace std;

const long long int M = 40;
const long long int N = 10e6 + 10;
long long int cnt;
long long int n, m;

int q[2][M];
int ord[N];

bool cra(int upper, int lower)
{
	int temp;

	if (lower <= 3)
		temp = lower + 3;
	else
		temp = lower - 3;

	for (int i = 0; i < m; i++)
	{
		if (q[0][i] == upper && q[1][i] == temp)
			return true;
		else if (q[0][i] == temp && q[1][i] == upper)
			return true;
	}
	return false;
}

void bfs(long long int i)
{
	if (i > n)
	{
		cnt++;
		cnt = cnt % 1000000007;
		return;
	}

	if(i>=2)
	for (int j = 1; j <= 6; j++)
	{
		if (!cra(j, ord[i - 1]))
		{
				ord[i] = j;
				bfs(i + 1);
		}
	}

	else if (i == 1)
		for (int j = 1; j <= 6; j++)
		{
			ord[i] = j;
			bfs(i + 1);
		}
}


long long fastPower(long long base, long long power) {
	long long result = 1;
	while (power > 0) {
		if (power % 2 == 1) {
			result = result * base % 1000000007;
		}
		power = power / 2;
		base = (base * base) % 1000000007;
	}
	return result;
}

int main()
{


	cin >> n >> m;

	for (int i = 0; i < m; i++)
		scanf("%d%d", &q[0][i], &q[1][i]);

	
	bfs(1);
	cout << cnt << endl;
	cnt=fastPower(4, n)*cnt;
	cout << cnt;
	return 0;
}