HDU 4389 X mod f(x)：枚舉 + 數位 DP 解決模運算計數

題目大意

求區間 [L, R] 中滿足 x % f(x) == 0 的數的個數，其中 f(x) 為 x 的十進制各位數字之和。數據範圍大，需高效算法。

核心思路：枚舉數位和 + 數位 DP

關鍵觀察

最大數位和為 9×9=81（10^9 以內）。枚舉目標數位和 S = 1..81，轉化為：計算區間內數位和為 S 且 x % S == 0 的數的個數。

DP 狀態定義

dp[pos][sum][modS][rem]：
- pos：當前處理到第幾位（從高到低）
- sum：已確定位的數位和
- modS：枚舉的目標數位和 S（固定）
- rem：當前前綴對 S 的餘數

轉移

枚舉當前位填 d (0..9)，更新 sum+d、(rem*10+d)%S。若 sum > S 剪枝。最終 pos==-1 時檢查 sum==S && rem==0。

完整代碼

#include <iostream>
#include <string.h>
#include <math.h>
using namespace std;
#define LL long long
int dp[11][82][82][82], dig[11];
int dfs(int cnt, int sum, int modS, int rem, bool limit) {
    if (cnt == -1) return (sum == modS && rem == 0);
    if (sum > modS) return 0;
    if (!limit && dp[cnt][sum][modS][rem] != -1) return dp[cnt][sum][modS][rem];
    int up = limit ? dig[cnt] : 9;
    int ans = 0;
    for (int i = 0; i <= up; i++)
        ans += dfs(cnt-1, sum+i, modS, (rem*10+i)%modS, limit && i==up);
    if (!limit) dp[cnt][sum][modS][rem] = ans;
    return ans;
}
int solve(int x) {
    if (x <= 0) return 0;
    int len = 0;
    while (x) { dig[len++] = x % 10; x /= 10; }
    int ans = 0;
    for (int S = 1; S <= 81; S++)
        ans += dfs(len-1, 0, S, 0, true);
    return ans;
}
int main() {
    memset(dp, -1, sizeof(dp));
    int L, R;
    while (cin >> L >> R)
        cout << solve(R) - solve(L-1) << endl;
    return 0;
}

優化細節

• 預處理 dp 為 -1 表示未計算，利用記憶化避免重複。
• limit 參數控制是否受上界限制，非受限狀態可複用。
• 枚舉 S 只需到 81，大幅減少狀態空間。

複雜度

狀態數：11×82×82×82 ≈ 600 萬，每狀態轉移 10 次，總操作 ~6000 萬，C++ 輕鬆通過。