HDU 3709 數位 DP：平衡數計數

題目

平衡數定義：存在一個支點位置，使得左側數字加權距離和等於右側。即對數字序列 d_k...d_0，存在 i 使 Σ_{ji} d_j*(j-i)。求區間 [x,y] (≤10^18) 內平衡數個數。T≤30。

核心技巧：狀態壓縮與差值

枚舉支點位置 pos。定義「力矩差」diff = Σ d_j*(pos-j)。平衡條件為 diff=0。數位 DP 狀態：dfs(len, pos, diff, tight)。
關鍵優化：diff 範圍有限（最大 9*18*18≈2916），可用數組記憶化。初始 diff=0，遞歸時根據位置更新 diff。最後統計 diff=0 的方案數。

代碼框架 (C++)

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
LL dp[20][20][3000]; // len, pos, diff+offset
int digits[20];
LL x, y;

LL dfs(int len, int pos, int diff, bool tight) {
    if (len < 0) return diff == 0;
    if (!tight && dp[len][pos][diff+1500] != -1) return dp[len][pos][diff+1500];
    int up = tight ? digits[len] : 9;
    LL ans = 0;
    for (int d = 0; d <= up; d++) {
        int ndiff = diff + (len - pos) * d; // 位置 len 相對支點 pos 的力矩貢獻
        ans += dfs(len-1, pos, ndiff, tight && d==up);
    }
    if (!tight) dp[len][pos][diff+1500] = ans;
    return ans;
}

LL solve(LL n) {
    if (n < 0) return 0;
    int len = 0;
    while (n) { digits[len++] = n%10; n/=10; }
    LL ans = 0;
    for (int pos = 0; pos < len; pos++) {
        memset(dp, -1, sizeof(dp));
        ans += dfs(len-1, pos, 0, true);
    }
    return ans + 1; // 包含 0
}

int main() {
    int T; scanf("%d", &T);
    while (T--) {
        scanf("%lld%lld", &x, &y);
        printf("%lld\n", solve(y) - solve(x-1));
    }
    return 0;
}