摘自： http://acm.hrbust.edu.cn/hcpc2012/index.php?act=showpost&p=15
本题是动态规划 + 矩阵乘法题
定义 f[i][0] 为走了 i 步恰好达到 S 的不同走法
定义 f[i][1] 为走了 i 步恰好达到 A 的不同走法
定义 f[i][2] 为走了 i 步恰好达到 B 的不同走法
定义 f[i][3] 为走了 i 步恰好达到 C 的不同走法
状态转义方程为：
f[i][0] = f[i – 1][1] + f[i – 1][2] + f[i – 1][3];
f[i][1] = f[i – 1][0] + f[i – 1][2] + f[i – 1][3];
f[i][2] = f[i – 1][0] + f[i – 1][1] + f[i – 1][3];
f[i][3] = f[i – 1][0] + f[i – 1][1] + f[i – 1][2];
由于 n 的规模达到 10 9 ，所以我们可以令
矩阵 A = [1 0 0 0] 表示走了 0 步时恰好到达 S, A, B, C 的不同走法，
那么每次状态转义相当于乘以矩阵 B ，其中：
B = [ 0 1 1 1
1 0 1 1
1 1 0 1
1 1 1 0 ]
可知，求走 n 步恰好到达 S 点的不同走法即是求 A * B n ，使用矩阵快速幂乘法即可。
1
/*
2
* 动态规划+矩阵乘法
3
*/
4
5
#include <cstdio>
6
#include <cstdlib>
7
#include <iostream>
8
9
using
namespace
std;
10
11
const
int
M =
1000000007
;
12
13
void
martix(unsigned
long
long
a[
4
][
4
],unsigned
long
long
b[
4
][
4
]) {
14
unsigned
long
long
c[
4
][
4
];
15
int
i, j, k;
16
for
(i=
0
; i<
4
; ++
i) {
17
for
(j=
0
; j<
4
; ++
j) {
18
c[i][j] =
0
;
19
for
(k=
0
; k<
4
; ++k) c[i][j] += a[i][k] * b[k][j] %
M;
20
}
21
}
22
for
(i=
0
; i<
4
; ++
i) {
23
for
(j=
0
; j<
4
; ++j) a[i][j] =
c[i][j];
24
}
25
}
26
27
unsigned
long
long
exp(unsigned
long
long
cs[
4
][
4
], unsigned
long
long
s[
4
][
4
], unsigned
long
long
n) {
28
while
(n) {
29
if
(n &
1
) martix(cs, s);
30
n >>=
1
;
31
martix(s, s);
32
}
33
return
cs[
0
][
0
] %
M;
34
}
35
36
int
main() {
37
int
t;
38
scanf (
"
%d
"
, &
t);
39
while
(t--
) {
40
int
n;
41
scanf (
"
%d
"
, &
n);
42
unsigned
long
long
cs[
4
][
4
] =
{
43
{
1
,
0
,
0
,
0
},
44
{
0
,
1
,
0
,
0
},
45
{
0
,
0
,
1
,
0
},
46
{
0
,
0
,
0
,
1
},
47
};
48
unsigned
long
long
s[
4
][
4
] =
{
49
{
0
,
1
,
1
,
1
},
50
{
1
,
0
,
1
,
1
},
51
{
1
,
1
,
0
,
1
},
52
{
1
,
1
,
1
,
0
},
53
};
54
unsigned
long
long
ans =
exp(cs, s, n);
55
printf (
"
%llu\n
"
, ans);
56
}
57
return
0
;
58
}
