蓝桥杯 垒骰子 矩阵快速幂 可惜不能提交

缘起

日常浪费生命~ 可惜, 此题蓝桥杯官网没有提交之处~ QAQ

分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
题目描述：

赌圣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>， 不能通过工程设置而省略常用头文件。  
提交时，注意选择所期望的编译器类型。

令

1
2
3
4
5
dp[i][n]是i面朝上, n个骰子的垒法数量. 则 i+3面就是第n个骰子的下面. 然后我们事先缓存与某个面的
对立面. 则就知道n-1个骰子某个面朝上的方法数. 然后周边四个面随便转动. 所以乘以4. 即
dp[i][n] = 4*(\Sigma_{对立面}dp[对立面][n-1])
于是我们就可以写下此DP式子的矩阵表达式. 而dp[任意一个面][1]=4, 所以答案是
矩阵的n-1次幂再乘以4^n模掉MOD=10^9 + 7后矩阵的所有元素之和

具体讲

为什么是与4可以衔接的面? 因为第n个骰子1朝上, 则第n个骰子4面朝下,则第n-1个骰子朝上的自然是需要和4可以衔接的面啦~ 而这个通过读入的矛盾对就可以得到. 其实就是图

于是不难写下如下代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
#include "stdafx.h"

#include <stdio.h>
#include <string.h>
#define LOCAL

typedef long long LL;

const LL MOD = 1e9 + 7,d  =6;

LL n,m, g[d+1][d+1];

void handle(int x,int y)
{
	if (x<=3)
	{
		g[x+3][y] = 0;
	}
	else
	{
		g[x-3][y] = 0;
	}
}

void m_mul(LL a[d+1][d+1], LL b[d+1][d+1])
{
	LL ans[d+1][d+1];
	memset(ans, 0, sizeof(ans));
	for (int i = 1; i<=d; i++)
	{
		for (int j = 1; j<=d; j++)
		{
			for (int k = 1;k<=d; k++)
			{
				ans[i][j]+=a[i][k]*b[k][j];
				ans[i][j]%=MOD;
			}
			ans[i][j]%=MOD;
		}
	}
	memcpy(a, ans, sizeof(ans));
}

void ksm(LL a[d+1][d+1], LL b) // a^b
{
	LL ans[d+1][d+1];
	for (int i = 1; i<=d; i++)
	{
		for (int j = 1; j<=d; j++)
		{
			ans[i][j] = i==j;
		}
	}
	while(b)
	{
		if (b&1)
		{
			m_mul(ans, a);
		}
		if (b>1)
		{
			m_mul(a,a);
		}
		b>>=1;
	}
	memcpy(a, ans, sizeof(ans));
}

LL q(LL b) // 计算 4^b 模掉MOD的余数
{
	LL ans = 1l,a=4L;
	while(b)
	{
		if (b&1)
		{
			ans = ans*a%MOD;
		}
		if (b>1)
		{
			a = a*a%MOD;
		}
		b>>=1;
	}
	return ans;
}

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
#endif
	scanf("%lld%lld", &n, &m);
	for (int i = 1;i<=d; i++)
	{
		for (int j = 1; j<=d; j++)
		{
			g[i][j] = 1;
		}
	}
	while(m--)
	{
		int x,y;
		scanf("%d%d", &x, &y); // x和y不能衔接
		handle(x,y); // 处理邻接矩阵
		handle(y,x);
	}
	LL xx = q(n);
	--n;
	ksm(g,n);
	LL ans = 0;
	for (int i = 1; i<=d; i++)
	{
		for (int j = 1;j<=d; j++)
		{
			ans+=g[i][j];
			ans%=MOD;
		}
	}
	printf("%lld\n", ans*xx%MOD);
	return 0;
}

反正测试数据通过了, ~可惜无处提交~ QAQ

ps: 最后说一句，其实和【1】本质是一个问题——就是有向图上固定长度的路径的数量.

参考

【1】https://yfsyfs.github.io/2019/09/19/sdutoj-3911-%E6%8C%87%E5%AE%9A%E9%95%BF%E5%BA%A6%E8%B7%AF%E5%BE%84%E6%95%B0-%E7%9F%A9%E9%98%B5%E5%BF%AB%E9%80%9F%E5%B9%82/