HDU 2510 符號三角形（幸運三角形）完整解題報告與打表優化

題目大意

給定正整數 n (n ≤ 24)，第一行有 n 個符號（+ 或 -），後續每行比上一行少一個符號。規則：兩個相同符號下方為 +，兩個不同符號下方為 -。求有多少種不同的第一行排列，使得整個三角形中 + 與 - 的總數相等。輸入多組 n，以 0 結束；輸出 n 及對應的合法三角形個數。

核心觀察與數學建模

將 + 映射為 0，- 映射為 1。根據規則，下一行符號即為上一行相鄰兩符號的**異或（XOR）運算**結果。因此整個三角形的生成過程等價於對第一行序列反覆進行相鄰異或，形成一個帕斯卡三角形結構的 XOR 變換。

三角形總元素數為 T = n(n+1)/2。要求 + 與 - 數量相等，即總和為 T/2（此時 T 必為偶數，故 n ≡ 0 或 3 (mod 4) 時才有解）。

解法一：DFS 回溯 + 剪枝（打表預計算）

由於 n ≤ 24，第一行共有 2^n 種組合，暴力枚舉不可行。但利用對稱性與剪枝，可在極短時間內完成全表預計算。

#include <cstdio>
int arr[26][26], ans[26], cnt;
void DFS(int n) {
    if (n > 24) return;
    for (int first = 0; first <= 1; ++first) {
        arr[1][n] = first;
        cnt += first;
        // 由第一行推導整個三角形
        for (int row = 2; row <= n; ++row) {
            arr[row][n-row+1] = arr[row-1][n-row+1] ^ arr[row-1][n-row+2];
            cnt += arr[row][n-row+1];
        }
        if (cnt * 2 == n*(n+1)/2) ++ans[n];
        DFS(n+1);
        // 回溯：減去本次貢獻
        cnt -= first;
        for (int row = 2; row <= n; ++row)
            cnt -= arr[row][n-row+1];
    }
}
int main() {
    DFS(1);
    for (int i = 1; i < 25; ++i) printf("%d, ", ans[i]);
    return 0;
}

關鍵優化：

• 只遞迴決定第一行的每一位，其餘行由 XOR 確定，狀態空間從 2^{n(n+1)/2} 降為 2^n。
• 使用全域陣列 arr 存儲中間值，回溯時僅需減去計數器，無需重置陣列。
• 預計算出的答案表僅 24 個整數，提交時直接查表 O(1)。

解法二：直接查表（AC 代碼）

#include <cstdio>
int ans[] = {0, 0, 0, 4, 6, 0, 0, 12, 40, 0, 0, 171, 410, 0, 0,
             1896, 5160, 0, 0, 32757, 59984, 0, 0, 431095, 822229};
int main() {
    int n;
    while (scanf("%d", &n), n)
        printf("%d %d\n", n, ans[n]);
    return 0;
}

此法利用預計算結果，程式極短、執行瞬間完成，為競賽中常用「打表」技巧。

樣本驗證

複雜度分析

• 預計算階段：約 Σ 2^n (n=1..24) ≈ 3.3×10^7 次迴圈，單機 < 0.5 秒完成。
• 線上查詢：O(1) 時間、O(1) 空間。

延伸思考

本題展示了「狀態壓縮 + 異或性質 + 打表」的經典組合。若 n 更大（如 1000），可考慮矩陣快速冪或組合數學公式進一步優化，但對於 n ≤ 24，DFS 打表已是最佳工程實踐。