---
# System prepended metadata

title: '演算法課程題解 - 動態規劃\: 轉移矩陣'
tags: [SCIST 演算法 題解]

---

# 演算法課程題解 - 動態規劃\: 轉移矩陣

# TOJ 416
## 題目
https://toj.tfcis.org/oj/pro/416/

你的魔力超級強大，可以輕鬆燒光敵軍，
但你的愛杖『超級智慧魔杖』（簡稱超智杖）卻承受不住你的全力。

你能施展火球術、超炎爆術、以及超大型魔法隕石術三種。
火球術不論施展幾次都沒問題，但超炎爆術只能連續使用兩次。
連續使用三次的話，超智杖就會過熱而毀損。
但只要中間隔一回合冷卻，就能夠再連續使用兩次。

而隕石術由於消耗魔力過大，對超智杖負荷太重，只能使用一次，
不管經過多少回合，只要再次使用，超智杖就會承受不住而折斷。

如果要施展 $n$ 回合的法術，你會有多少種不同的方式可以燒掉敵軍?
## 想法2 (100%) By Koios
這邊要改用轉移矩陣來找答案
我是第一次用轉移矩陣來解競賽題，所以詳細解釋一下

這裡以費氏序列舉例
$$
f(x) = f(x-1) + f(x-2)
$$

改用矩陣的方式來表達的話，可以寫成
$$
f(x) = \begin{bmatrix} f(x-1) & f(x-2)\end{bmatrix} \begin{bmatrix} 1 \\ 1 \end{bmatrix}
$$

接下來嘗試讓結果也變成形如 $\begin{bmatrix} f(x-1) & f(x-2)\end{bmatrix}$ 的樣子，這樣我們之後就可以通用這個矩陣來求下一項的答案
$$
\begin{bmatrix} f(x) & f(x-1)\end{bmatrix} = \begin{bmatrix} f(x-1) & f(x-2)\end{bmatrix} \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}
$$

也就是說
$$
\begin{bmatrix} f(1) & f(0)\end{bmatrix} \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix} ^{n} = \begin{bmatrix} f(1+n) & f(n)\end{bmatrix}
$$

回到這一題，我們總共有 $6$ 種狀態，分別從 $dp[i][0][0]$ 到 $dp[i][2][1]$，可以改寫成矩陣的樣子

$$
\begin{bmatrix}
f(i+1, 0, 0) \\ f(i+1, 0, 1) \\ f(i+1, 1, 0) \\ f(i+1, 1, 1) \\ f(i+1, 2, 0) \\ f(i+1, 2, 1)
\end{bmatrix} =
\begin{bmatrix}
1 & 0 & 1 & 0 & 1 & 0 \\
1 & 1 & 1 & 1 & 1 & 1 \\
1 & 0 & 0 & 0 & 0 & 0 \\
0 & 1 & 0 & 0 & 0 & 0 \\
0 & 0 & 1 & 0 & 0 & 0 \\
0 & 0 & 0 & 1 & 0 & 0
\end{bmatrix}
\begin{bmatrix}
f(i, 0, 0) \\ f(i, 0, 1) \\ f(i, 1, 0) \\ f(i, 1, 1) \\ f(i, 2, 0) \\ f(i, 2, 1)
\end{bmatrix}
$$

也就是說
$$
\begin{bmatrix}
f(n+1, 0, 0) \\ f(n+1, 0, 1) \\ f(n+1, 1, 0) \\ f(n+1, 1, 1) \\ f(n+1, 2, 0) \\ f(n+1, 2, 1)
\end{bmatrix} =
\begin{bmatrix}
1 & 0 & 1 & 0 & 1 & 0 \\
1 & 1 & 1 & 1 & 1 & 1 \\
1 & 0 & 0 & 0 & 0 & 0 \\
0 & 1 & 0 & 0 & 0 & 0 \\
0 & 0 & 1 & 0 & 0 & 0 \\
0 & 0 & 0 & 1 & 0 & 0
\end{bmatrix}^{n}
\begin{bmatrix}
f(0, 0, 0) \\ f(0, 0, 1) \\ f(0, 1, 0) \\ f(0, 1, 1) \\ f(0, 2, 0) \\ f(0, 2, 1)
\end{bmatrix}
$$

令 $A = \begin{bmatrix}
1 & 0 & 1 & 0 & 1 & 0 \\
1 & 1 & 1 & 1 & 1 & 1 \\
1 & 0 & 0 & 0 & 0 & 0 \\
0 & 1 & 0 & 0 & 0 & 0 \\
0 & 0 & 1 & 0 & 0 & 0 \\
0 & 0 & 0 & 1 & 0 & 0
\end{bmatrix}$

接下來用到矩陣快速冪來快速算出 $A^n$
概念跟快速冪相同
遇到次方 $n$ 是偶數，就先算 $n/2$ 次方的答案，再把該答案平方就會是整體的答案
反之次方 $n$ 是奇數，就算出 $n-1$ 次方的答案，再跟 $A$ 相乘一次就會是整體的答案
不過需要實作一下矩陣乘法運算

### 程式碼
```cpp=
//By Koios1143
#include<iostream>
using namespace std;
const long long Mod = 1000000007;
int n;

long long A[6][6] = {
{1, 0, 1, 0, 1, 0},
{1, 1, 1, 1, 1, 1},
{1, 0, 0, 0, 0, 0},
{0, 1, 0, 0, 0, 0},
{0, 0, 1, 0, 0, 0},
{0, 0, 0, 1, 0, 0}};

long long M[6] = {1, 1, 1, 0, 0, 0};

// (6x6) x (6x6) 矩陣乘法
void mul(long long (*p)[6], long long (*q)[6], long long (*res)[6], long long Mod){
	for(int i=0 ; i<6 ; i++){
		for(int j=0 ; j<6 ; j++){
			res[i][j] = 0;
			for(int k=0 ; k<6 ; k++){
				res[i][j] += p[i][k] * q[k][j];
				res[i][j] %= Mod;
			}
		}
	}
}

// (6x6) x (6x1) 矩陣乘法
void mul2(long long (*p)[6], long long *q, long long *res, long long Mod){
	for(int i=0 ; i<6 ; i++){
		res[i] = 0;
		for(int j=0 ; j<6 ; j++){
			res[i] += p[i][j] * q[j];
			res[i] %= Mod;
		}
	}
}

// (6x6) x (6x6) 矩陣快速冪
void qpow(long long (*p)[6], long long q, long long (*res)[6], long long Mod){
	long long tmp[6][6];
	if(q == 1){
		for(int i=0 ; i<6 ; i++){
			for(int j=0 ; j<6 ; j++){
				res[i][j] = p[i][j];
			}
		}
		return;
	}
	if(q % 2 == 0){
		qpow(p, q/2, tmp, Mod);
		mul(tmp, tmp, res, Mod);
	}
	else{
		qpow(p, q-1, tmp, Mod);
		mul(p, tmp, res, Mod);
	}
}


int main(){
	while(cin>>n){
		// 避免詢問 n-1 時為 0
		if(n == 1){
			cout<<3<<"\n";
			continue;
		}
		
		long long res[6][6], res2[6], ans = 0;
		// 計算 A 的 n-1 次方
		qpow(A, n-1, res, Mod);
		// 再跟原矩陣相乘
		mul2(res, M, res2, Mod);
		for(int i=0 ; i<6 ; i++){
			ans += res2[i];
			ans %= Mod;
		}
		cout<<ans<<"\n";
	}
	return 0;
}
```

### 時間複雜度分析
一次矩陣乘法所需的操作數量約為 $6 \times 6 \times 6$
矩陣快速冪操作次數約為 $log_{2}n$，每次會做一次矩陣乘法，總操作數約為 $216log_{2}n$，計為 $O(log_{2}n)$
最後跟原矩陣相乘所需的操作數量約為 $6 \times 6 \times 1$，計為 $O(1)$
每筆測資總時間複雜度約為 $O(log_{2}n)$

###### tags: `SCIST 演算法 題解`