題意#
你要建構一座寬度為 2、高度為 \( n \) 的積木塔。
你手上有無窮無盡的積木，這些積木的長寬都是整數。每往上疊一層，你可以選擇放兩塊寬度為 1 的積木，也可以直接放一塊寬度為 2 的積木。
不僅如此，積木還可以垂直相連！只要寬度相同，積木可以無限往上延伸。在這些豐富的組合之下，請問總共有幾種建構這座塔的方式？答案須對 \( 10^9 + 7 \) 取餘數。
思路#
這題乍看之下很複雜，因為不僅有寬度切割的問題，還有垂直延伸的問題。但只要把狀態定義清楚，其實就是很標準的狀態壓縮/轉移 DP。
對於每一層（高度 \( i \)），其實只有兩種截面狀態：
- 狀態 0：這層是由一整塊寬度為 2 的積木組成。
- 狀態 1：這層是從中間切開，由兩塊寬度為 1 的積木組成。
我們定義 dp[0][i] 為「蓋到高度 \( i \) 時，頂層是狀態 0 的所有可能數量」，以及 dp[1][i] 為「頂層是狀態 1 的所有可能數量」。
接著來思考從第 i-1 層蓋上第 i 層的狀態轉移：
如果要讓第 i 層變成狀態 0（一整塊）：
- 如果下層也是一整塊，我們可以選擇「讓這塊原本的積木繼續往上長」或是「放一塊新的大積木在上面」，共 2 種蓋法。
- 如果下層是兩半，我們只能「放一塊新的大積木蓋在它們上面」，共 1 種蓋法。
所以dp[0][i] = 2 * dp[0][i-1] + dp[1][i-1]。
如果要讓第 i 層變成狀態 1（切兩半）：
- 如果下層也是兩半，我們對左右兩塊各有 2 種選擇（繼續往上長、或是疊一塊新的），根據乘法原理，總共有 \( 2 \times 2 = 4 \) 種蓋法。
- 如果下層是一整塊大積木，我們只能「在上面疊兩塊新的小積木」，只有 1 種蓋法。
所以dp[1][i] = dp[0][i-1] + 4 * dp[1][i-1]。
因為有很多筆測資，最好的作法就是一開始先建表算好高度 1 到 1000000 的所有答案，後面直接以 \( O(1) \) 的速度查表輸出。
程式碼#
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define INF LONG_LONG_MAX/1000
#define WA() cin.tie(0)->sync_with_stdio(0)
#define all(x) (x).begin(), (x).end()
#define int long long
#define PII pair<int, int>
signed main() { WA();
int p = 1e9+7;
// dp[0] 表示當層是一整塊；dp[1] 表示當層切成左右兩半
vector<vector<int>> dp(2, vector<int>(1000000+1));
// 初始化第一層，一整塊和切兩半都各有 1 種擺法
dp[0][1] = 1; dp[1][1] = 1;
// 預先建表，算出高度到 10^6 的所有組合數
for (int i = 2; i <= 1000000; i++) {
// 狀態 0 轉移：下層一整塊有 2 種接法，下層切一半有 1 種接法
dp[0][i] = (2 * dp[0][i-1] % p + dp[1][i-1]) % p;
// 狀態 1 轉移：下層一整塊有 1 種接法，下層切一半有 4 種接法
dp[1][i] = (dp[0][i-1] + 4 * dp[1][i-1] % p) % p;
}
int t;
for (cin >> t; t--;) {
int n; cin >> n;
// 把頂層是狀態 0 和狀態 1 的答案相加即為總數
cout << (dp[0][n] + dp[1][n]) % p << '\n';
}
}
