摘自： 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
}
?
?
?
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
