稱一個數為「平衡數」，若存在某位 pos 使得左側數字 × 距離之和 = 右側數字 × 距離之和（力矩平衡）。給定區間 [L, R] (R ≤ 10¹⁸)，求區間內平衡數個數。
dp[pos][pivot][torque]：正在處理第 pos 位（從低位向高位），平衡點固定為 pivot，已處理低位產生的力矩和為 torque（左側為正，右側為負），滿足條件的方案數。
轉移：枚舉當前位 d (0..9)，新力矩 torque + (pos - pivot) * d。若 torque < 0 剪枝（右側力矩過大無法被左側抵消）。
邊界：pos == -1 時 torque == 0 返回 1，否則 0。
數字長度 ≤ 19，平衡點 pivot 可為 0~18。對每個 pivot 獨立跑 DP，結果求和。注意全 0 的情況會被多次計算（每個 pivot 都算一次），需減去 len-1 次重複。
#includeusing namespace std; typedef long long LL; int bit[20]; LL dp[20][20][1500]; // pos(0..18), pivot(0..18), torque(0..1458=9*18*9) int targetPivot; LL dfs(int pos, int torque, bool limit) { if (pos == -1) return torque == 0; if (!limit && dp[pos][targetPivot][torque] != -1) return dp[pos][targetPivot][torque]; int up = limit ? bit[pos] : 9; LL ans = 0; for (int d = 0; d <= up; ++d) { int nTorque = torque + (pos - targetPivot) * d; if (nTorque < 0) continue; // 剪枝 ans += dfs(pos-1, nTorque, limit && d==up); } if (!limit) dp[pos][targetPivot][torque] = ans; return ans; } LL solve(LL x) { if (x < 0) return 0; int len = 0; if (x == 0) bit[len++] = 0; while (x) { bit[len++] = x%10; x/=10; } LL ans = 0; for (int p = 0; p < len; ++p) { targetPivot = p; ans += dfs(len-1, 0, false); } ans -= len - 1; // 扣除 0 的重複計算 return ans; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); memset(dp, -1, sizeof(dp)); int T; cin >> T; while (T--) { LL L, R; cin >> L >> R; cout << solve(R) - solve(L-1) << '\n'; } return 0; }
9 * 18 * 9 = 1458，DP 表 [20][20][1500] 足夠。targetPivot 全局變量避免傳參開銷。nTorque < 0：右側力矩為負且絕對值過大，後續高位只能增加左側力矩（正），無法平衡。solve(0)=1，區間查詢用 solve(R) - solve(L-1)。HDU 3709 是「數位 DP + 自定義物理約束（力矩）」的經典題。核心模板：枚舉關鍵參數（平衡點）+ 狀態攜帶累積物理量（力矩）+ 記憶化遞歸 + 物理剪枝。同套路解決 HDU 3709、Codeforces 數位 DP 物理約束問題。
