HDU ACM 1297 Children's Queue：大數加法與遞推關係

題目大意

有 N 個孩子排隊，男孩（B）女孩（G）。要求不能有單獨一個女孩相鄰（即女孩必須成雙成對出現）。求合法隊形數。N ≤ 1000，答案極大，需大數輸出。

遞推關係推導

設 F(N) 為長度 N 的合法隊形數。考慮最後一位：

1. 最後是男孩：前 N-1 任意合法 → F(N-1)。
2. 最後是女孩：倒數第二也必須是女孩（成對）。
   • 若倒數第三是男孩：前 N-3 任意合法 → F(N-3)？不，實際推導發現是 F(N-2)。
   • 若倒數第三也是女孩，則倒數第四必須是男孩 → F(N-4)。

綜合得遞推式：

F(N) = F(N-1) + F(N-2) + F(N-4)

初始值：F(0)=1, F(1)=1, F(2)=2, F(3)=4, F(4)=7。

大數加法實現

用 char num[1001][300] 存儲每個 F(i) 的十進制字符串（低位在前或後均可），手寫逐位加法帶進位。

完整代碼（C++）

#include <iostream>
#include <cstring>
using namespace std;
char num[1001][300];

void add(int x, int y) {          // num[x] += num[y]
    int tmp[300] = {0};
    int len1 = strlen(num[x]), len2 = strlen(num[y]);
    int i = len1-1, j = len2-1, k = 0;
    while (i >= 0 && j >= 0) tmp[k++] = num[x][i--]-'0' + num[y][j--]-'0';
    while (i >= 0) tmp[k++] = num[x][i--]-'0';
    while (j >= 0) tmp[k++] = num[y][j--]-'0';
    for (i = 0; i < k-1; ++i) {
        if (tmp[i] >= 10) { tmp[i+1] += tmp[i]/10; tmp[i] %= 10; }
    }
    if (tmp[k-1] >= 10) { tmp[k] = tmp[k-1]/10; tmp[k-1] %= 10; k++; }
    i = k-1; j = 0;
    while (i >= 0) num[x][j++] = tmp[i--] + '0';
    num[x][k] = '\0';
}

int main() {
    num[0][0] = num[1][0] = '1'; num[0][1] = num[1][1] = '\0';
    num[2][0] = '2'; num[2][1] = '\0';
    num[3][0] = '4'; num[3][1] = '\0';
    num[4][0] = '7'; num[4][1] = '\0';
    for (int i = 5; i <= 1000; ++i) {
        strcpy(num[i], num[i-1]);
        add(i, i-2);
        add(i, i-4);
    }
    int n;
    while (cin >> n) cout << num[n] << endl;
    return 0;
}

複雜度

• 預處理：O(N * L)，L ≈ 0.208N 位（增長率約 1.236ⁿ）。
• 查詢：O(L) 輸出。
• 空間：O(N * L) ≈ 30 萬字符，極小。

關鍵點

1. 遞推式推導是核心，畫圖分類討論最不易錯。
2. 大數加法模板要熟練，注意進位傳播與字符串反轉存儲。
3. 預處理所有 N≤1000，多測試用例 O(1) 回答。