2015年第六届蓝桥杯C++B组I题

2015年第六届蓝桥杯C++B组I题

垒骰子

赌圣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 ， 不能通过工程设置而省略常用头文件。

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

2015年得真题还是挺简单的=-=压轴题都是模板题。
做了几次真题之后发现了一个规律。每次都是难易难易。2019相对比较简单=-=那么2020.。。就应该比较难了把。。这里的难相对我来说的啊哈。。。。
2015年得真题做到第九题卡住了。我以为这次真题还挺简单。涉及到了我的知识盲区，哇哦。幸好我坚持下来了。

矩阵快速幂，哇。其实模板一写出来真的跟快速幂差不多=-=啊哈哈哈开心，一个下午啊啊啊

这道题就是道模板题啊哈哈哈

我当时一直在想为啥要乘4^n，而不是5 ^ n，想了很久=-=后来枚举列了一下啊啊好蠢啊。有一个面是不能成立的，然后已经算了一个面，然后还有四个面可以旋转，这个比较好想了哈
这个最后乘4^n的地方也是要用快速幂的。乘法逆元。
矩阵快速幂就是把数字改为矩阵的运算。然后在乘法逆元中的1对应矩阵的单位矩阵，位数按照求得维数来。当初接触矩阵快速幂的时候感觉模模糊糊。然后上个学期学完线代以后。（虽然老师讲了跟没讲一样）
再接触。感觉理解透彻了简单了很多啊哈哈哈
开心

然后就是矩阵的运算了。
设dp[i][j]表示i的高度j朝上的方案数
这里是一个累加的过程，只跟下面一层有关
dp[i][j] = 求和（dp[i-1][j])六个面

矩阵T中的元素表示T[i][j]为第i面和第j面冲突
矩阵A中的元素表示A[i][j]为第1个骰子，j面朝上的摆法。
矩阵T和矩阵A相乘一次表示两个骰子的方案数
所以需要得到n个骰子得方案数就是乘以n-1次就可以啦。
就是求T矩阵得n-1次方。然后再乘以A矩阵。最后乘法逆元快速幂求一下4^n次方得到答案。
最最后累加维护ans就可以啦
记得每次都要取模哦~

代码部分：

#include <bits/stdc++.h>
typedef long long ll;
const int mod = 1e9 + 7;
using namespace std;

int fro[7] = {0, 4, 5, 6, 1, 2, 3};
ll ans;

struct matrix
{
	int n, m;
	ll a[7][7];
};

matrix matrix_unit()
{
	matrix res;
	res.n = 6;
	res.m = 6;
	for (int i = 1; i <= res.n; i++)
	{
		for (int j = 1; j <= res.m; j++)
		{
			if (i == j)
			{
				res.a[i][j] = 1;
			}
			else
			{
				res.a[i][j] = 0;
			}
		}
	}
	return res;
}

matrix matrix_mul(matrix A, matrix B)
{
	matrix C;
	C.n = A.n;
	C.m = B.m;
	for (int i = 1; i <= C.n; i++)
	{
		for (int j = 1; j <= C.m; j++)
		{
			C.a[i][j] = 0;
			for (int k = 1; k <= A.m; k++)
			{
				C.a[i][j] += A.a[i][k] * B.a[k][j] % mod;
			}
		}
	} 
	return C;
}

matrix matrix_pow(matrix A, int n)
{
	matrix res = matrix_unit();
	matrix temp = A;
	while (n)
	{
		if (n & 1)
		{
			res = matrix_mul(res, temp);
		}
		temp = matrix_mul(temp, temp);
		n >>= 1;
	}
	return res;
}

ll pow_mod(ll a, int n)
{
	ll res = 1;
	while (n)
	{
		if (n & 1)
		{
			res = res * a % mod;
		}
		a = a * a % mod;
		n >>= 1;
	}
	return res;
}

int main()
{
	int m, n;
	cin >> n >> m;
	matrix col;
	col.n = 6;
	col.m = 6;
	for (int i = 0; i < 7; i++)
	{
		for (int j = 0; j < 7; j++)
		{
			col.a[i][j] = 1;
		}
	}
	int u, v;
	for (int i = 0; i < m; i++)
	{
		scanf ("%d%d", &u, &v);
		col.a[fro[u]][v] = 0;
		col.a[fro[v]][u] = 0;
	}
	matrix res, base;
	for (int i = 1; i <= 6; i++)
	{
		base.a[1][i] = 1;
	}
	base.n = 1;
	base.m = 6;
	res = matrix_pow(col, n - 1);
	res = matrix_mul(base, res);
	
	for (int i = 1; i <= 6; i++)
	{
		ans = (ans + res.a[1][i]) % mod;
	}
	ans = ans * pow_mod(4, n) % mod;
	cout << ans << endl;
	return 0;
}