蓝桥杯真题——垒骰子

[第6届-A-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>， 不能通过工程设置而省略常用头文件。

提交时，注意选择所期望的编译器类型。

思想：

①当堆放方式(相邻的两个骰子哪两个面挨着)确定，每个骰子有四个侧面可以旋转，所以结果应该是4^n * 堆放方式。

②动态规划的思想， 每次加一个骰子到最顶端，考虑6个面，每一个面可以有多少种方式。 此时则需要考虑已经搭好的骰子顶端没种面朝上的可能方式数量。这样便出现了递推关系式：面[i]方式数=已经搭好, 面[i]可以接触的面,朝上的数量累加。

③例如测试用例所示：第二层放面1的时候就=1+1+1+1+1（这里没有加面2）;=>面[1]=5，面[2]=5，面[3]=6，面[4]=6，  面[5]=6，面[6]=6；则由于对面关系，第二层搭建完毕后，向上面为面[i]的方式数：面[1]=6，面[2]=6，面[3]=6，面[4]=5，  面[5]=5，面[6]=6；则第三层放面1的时候就=6+6+5+5+6（这里没有加面2）。

④详细的可以看代码，这个规律懂了之后看代码应该就没有问题了。

⑤我代码时间复杂度最大o(54n)，最小o(18n)，但是这样额复杂度是过不了10^7及以上的数据的，希望有更好解法的同学，评论给我。

代码：

#include <iostream>  
#include <vector>
using namespace std;  

vector<int> can[7];//存can[i]能和哪些点挨着
int up[7]={1,1,1,1,1,1,1};
int temp[7]={1}; 
int k=4;

const int MOD=1000000007;

void init()//初始化都可挨着 
{	
	for(int i=1; i<=6; i++)
		for(int j=1; j<=6; j++)
			can[i].push_back(j);

}
void dele(int side1, int side2)//删除不可挨着的点
{ 
	for(vector<int>::iterator it=can[side1].begin();it!=can[side1].end(); it++)
		if(*it==side2)
		{
			can[side1].erase(it);
			break;
		}
			
	for(vector<int>::iterator it=can[side2].begin(); it!=can[side2].end(); it++)
		if(*it==side1)
		{
			can[side2].erase(it);
			break;
		}	
} 
void fun(int n)
{
	for(int i=2; i<=n; i++)
	{
		//计算出第i层骰子每种底面的可能次数 
		for(int j=1; j<=6; j++)
		{
			temp[j]=0;
			for(vector<int>:: iterator it=can[j].begin(); it!=can[j].end(); it++)
				temp[j]+=up[*it];
		}
		//转化为第i层骰子顶面的可能次数
		up[1]=temp[4]%MOD; 
		up[2]=temp[5]%MOD; 
		up[3]=temp[6]%MOD; 
		up[4]=temp[1]%MOD; 
		up[5]=temp[2]%MOD; 
		up[6]=temp[3]%MOD; 
		//4^n
		k=k*4;	k=k%MOD; 
	}
	int ans=0;
	for(int j=1; j<=6; j++)
			ans+=up[j]; 
	cout<<(ans*k)%MOD;
}
int main(int argc, char** argv)   
{  
	init();	
	
	int n, m;
	cin>>n>>m;
	
	for(int i=0;i<m; i++)
	{
		int side1, side2;
		cin>>side1>>side2;
		dele(side1,side2);
	} 

	fun(n);

    return 0;  
}