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

这道题首先要会递推的做法。
很自然的,我们可以用$f[i][j]$表示垒了$i$个骰子,并且最上面的骰子$j$面朝上。
那么递推式就是$$f[i][j]=\sum_{k=1}^{6} f[i-1][k]\quad coop[op[j]][k]$$
其中$op[j]$表示$j$的背面,$coop[op[j]][k]$就表示$j$的背面是可以跟$k$放在一起的。
这样每次没有讨论侧面的朝向,所以最后乘以$4^n$。
如果想要实现的好的话还要使用滚动数组 滚动数组资料

放一个搜到的代码吧。。。

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
#include <iostream>
using namespace std;

// ...冲突记录: Compact[i][j]=false代表点数为i的面与点数为j的面存在冲突
bool Compact[7][7];

// ...Parner[i]=j代表 点数为i的面 的对立面点数为j
const int Parner[7]={ 0,4,5,6,1,2,3 };
const long long MOD = 1000000007;

int main(int argc, char** argv)
{
long long N; // 骰子高度
int M; // 冲突组数
int s1,s2;
cin >> N >> M;
for( int i = 0; i < 7; ++i)
for( int j = 0; j < 7;++j)
Compact[i][j]=true;

for( int i = 0; i < M; ++i ) {
cin >> s1 >> s2;
// ...点数为s1的面与点数为s2的面存在冲突
Compact[s1][s2] = Compact[s2][s1] = false;
}
long long dp[2][7]; // 滚动数组
long long C = 4;
int e = 0; // 滚动标志
for( int i = 1; i < 7; ++i )
dp[e][i] = 1;

// dp[i][j]代表高度为i的,顶面点数为j的叠骰子方案数
// 在这里忽略每个骰子可以四面转向的情况, 把该情况留到最后乘上去就可以了
int j,k;
for( long long i = 2; i <= N; ++i ){
e = 1-e; // ...滚动处理
C = (C*4)%MOD;
for( j = 1; j < 7; ++j ){
dp[e][j] = 0;
for( k = 1; k < 7; ++k)
if( Compact[ Parner[j] ][k] )
dp[e][j] += dp[1-e][k];
dp[e][j]%=MOD;
}

}
int sum=0;
for( int i = 1; i < 7; ++i)
sum = (sum+dp[e][i])%MOD;
sum = (sum*C)%MOD;
cout << sum;
return 0;
}

核心代码的复杂度$T(n)=36n$,就算给了2s肯定也是不能全通过的,我们需要一个更快的方法。
分析可以发现其实每一步递推对应的关系都是一样的,就是最开始给出的那些关系。
所以我们可以用矩阵来进行递推,再使用快速幂即可 矩阵递推资料

代码用了模板技术,大家凭感觉吧。。。

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
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int MO=1e9+7;
const int opps[]={0,4,5,6,1,2,3};

struct Mat {
int r,c;
ll el[10][10];
Mat() {}
Mat(ll x) {
r=c=6;
memset(el,0,sizeof(el));
for (int i=1;i<=r;i++) {
el[i][i]=x;
}
}
Mat(int _r,int _c,ll x) {
r=_r;c=_c;
for (int i=1;i<=r;i++) {
for (int j=1;j<=c;j++) {
el[i][j]=x;
}
}
}
Mat operator *(const Mat &b) {
Mat res(r,b.c,0);
for (int i=1;i<=r;i++) {
for (int j=1;j<=b.c;j++) {
for (int k=1;k<=c;k++) {
res.el[i][j]+=el[i][k]*b.el[k][j];
}
}
}
return res;
}
Mat operator %(const int Mo) {
for (int i=1;i<=r;i++) {
for (int j=1;j<=c;j++) {
el[i][j]=el[i][j]%Mo;
}
}
return (*this);
}
void print() {
for (int i=1;i<=r;i++) {
for (int j=1;j<=c;j++) {
printf("%I64d ",el[i][j]);
}
puts("");
}
}
};

template <class DataType>
DataType fpow(DataType x,int n)
{
DataType res(1);
while (n) {
if (n&1) {
res=x*res%MO;
}
x=x*x%MO;
n>>=1;
}
return res;
}

int main()
{
int n,m;
Mat coop(6,6,1);
scanf("%d%d",&n,&m);
for (int i=1;i<=m;i++) {
int x,y;
scanf("%d%d",&x,&y);
coop.el[x][opps[y]]=0;
coop.el[y][opps[x]]=0;
}
coop=fpow(coop,n-1);
Mat cnt(6,1,1);
cnt=coop*cnt%MO;
ll ans=0,fo=4;
for (int i=1;i<=6;i++) {
ans=(ans+cnt.el[i][1])%MO;
}
ans=ans*fpow(fo,n)%MO;
printf("%I64d\n",ans);
return 0;
}