T6:填数

题目思路（DP）

相邻两格的和为偶数 ⇔ 两格同奇偶性。

可填数字只有 1, 2, 3：

• 奇数：1, 3（2 个选择）
• 偶数：2（1 个选择）

因此一旦第 1 格确定了奇偶性，后面所有格子的奇偶性都被固定（必须全部同奇或全偶）。

---

动态规划写法

设：

• odd[i]：前 i 个格子填完，且第 i 个格子是奇数的方案数
• even[i]：前 i 个格子填完，且第 i 个格子是偶数的方案数

转移（相邻必须同奇偶）：

• odd[i] = odd[i-1] * 2（第 i 格是奇数，有 1 或 3 两种）
• even[i] = even[i-1] * 1（第 i 格是偶数，只能填 2）

初始化：

• odd[1] = 2
• even[1] = 1

答案：

• odd[n] + even[n]

---

普通数组 C++ 代码

n ≤ 50，结果最大是 2^50 + 1，用 unsigned long long 足够。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;

    unsigned long long odd[55], even[55];
    odd[1] = 2;   // {1,3}
    even[1] = 1;  // {2}

    for (int i = 2; i <= n; i++) {
        odd[i] = odd[i - 1] * 2;
        even[i] = even[i - 1];  // *1
    }

    cout << odd[n] + even[n] << "\n";
    return 0;
}