LightOJ 1205 Palindromic Numbers：數位 DP 計數回文數

題目重述

給定區間 [x, y]，求區間內回文數的個數。多組測試數據，x, y 可達 10¹⁸ 級別，需用 64 位整數（long long / __int64）。

數位 DP 核心思想

回文數的特徵：從最高位到最低位讀，與從最低位到最高位讀完全相同。即第 i 位數字必須等於第 len-i+1 位數字（len 為總位數）。

我們用遞歸函數 dfs(pos, len, zero, tight) 從高位向低位逐位填數：

• pos：當前正在填第 pos 位（從高位 len 遞減到 1）。
• len：目標數字的總位數（固定）。
• zero：前導零標記，true 表示目前還全是前導零。
• tight：上界緊縮標記，true 表示前綴已達到上界，當前位不能超過上界對應位。

狀態轉移關鍵邏輯

1. 前導零階段（zero==true）：
   • 填 0：繼續前導零，len 不變（實際長度還未確定）。
   • 填非 0：結束前導零，確定總長度 len，記錄該位數字到 ok[pos]。
2. 非前導零階段（zero==false）：
   • 計算對稱位置 mirror = len - pos + 1。
   • 若 pos > mirror（在中點右側）：自由填 0~9，記錄 ok[pos]。
   • 若 pos == mirror（中點，奇數長度）：自由填 0~9，無對稱約束。
   • 若 pos < mirror（在中點左側）：必須填 ok[mirror]，否則不構成回文。

記憶化優化

dp[pos][len] 存儲「剩餘 pos 位、總長度 len、非緊縮、非前導零」的方案數。狀態數極小（pos, len ≤ 19），瞬間算完。

完整代碼（C++，含詳註）

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

int64 dp[22][22];   // dp[pos][len]
int num[22];        // 上界各位數字（高位在前）
int ok[22];         // 已確定的右半部數字

// pos: 當前處理到第 pos 位（從高位 len 遞減到 1）
// len: 目標總長度
// zero: 是否仍在前導零
// tight: 是否受上界限制
int64 dfs(int pos, int len, bool zero, bool tight) {
    if (pos == 0) return 1;  // 所有位填完，構成一個合法數
    if (!tight && !zero && dp[pos][len] != -1) return dp[pos][len];

    int limit = tight ? num[pos] : 9;
    int64 res = 0;

    for (int d = 0; d <= limit; ++d) {
        bool nzero = zero && (d == 0);
        bool ntight = tight && (d == limit);

        if (nzero) {
            // 仍在前導零：長度不確定，傳遞 len-1（因為實際長度可能更短）
            res += dfs(pos-1, len-1, nzero, ntight);
        } else {
            int mirror = len - pos + 1;
            if (pos > mirror) {           // 右半部：自由選，記錄供左半部對稱
                ok[pos] = d;
                res += dfs(pos-1, len, nzero, ntight);
            } else if (pos == mirror) {   // 中點（奇數長度）：自由選
                res += dfs(pos-1, len, nzero, ntight);
            } else {                      // 左半部：必須等於對應右半部
                if (ok[mirror] == d)
                    res += dfs(pos-1, len, nzero, ntight);
            }
        }
    }

    if (!tight && !zero) dp[pos][len] = res;
    return res;
}

int64 solve(int64 x) {
    if (x < 0) return 0;
    int len = 0;
    while (x) {
        num[++len] = x % 10;
        x /= 10;
    }
    return dfs(len, len, true, true);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    memset(dp, -1, sizeof(dp));
    int T; cin >> T;
    for (int cs = 1; cs <= T; ++cs) {
        int64 x, y; cin >> x >> y;
        if (x > y) swap(x, y);
        cout << "Case " << cs << ": " << solve(y) - solve(x-1) << "\n";
    }
    return 0;
}

關鍵細節總結

• 前導零處理：zero 標記區分「還沒開始」與「已經開始」，避免將 00100 視為 5 位數。
• 對稱約束：用 ok[] 數組記錄右半部選擇，左半部強制匹配。
• 長度動態確定：第一個非零位決定實際長度 len，前導零階段傳 len-1 兼容更短長度。
• 上界緊縮：標準數位 DP tight 技巧，確保不超過 x。
• 64 位整數：答案可能超過 2³¹，必須用 long long / %lld。

複雜度

狀態數 O(20×20)，每狀態轉移 O(10)，預處理 O(1)，單次查詢 O(位數)，極快。