# 演算法課程題解 - 動態規劃\: 轉移矩陣
# 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 演算法 題解`
Sign in with Wallet
Connect another wallet