目录

• Description
• State
• Input
• Output
• Solution
• Code

Description

State

\(1<=a<=b<=10^{18}\)

Input

? 10 19

Output

? 3

Solution

题目偏思维，去掉了麻烦的前导零，代码实现比较简单。

在使用数位dp 的过程中，光标 \(pos\) 移动的位置，我们可以得到的是前 \(pos\) 高位的各位之和 ，记为 \(sum\);

而当 \(pos\) 移动到最低位时，我们可以知道这个数 \(x\) 是多少，以及这个数的 \(sum\)，之后 \(x\%sum==0\) 便可以对答案进行贡献，也就是说并不需要知道 \(x\) 的值，只需要知道 \(x\%sum\) 的值即可，但是在 \(pos\) 光标移动过程中并不知道 \(pos\) 之后的各个数位为多少，也就是说 \(sum\) 并不知道，但是可以枚举 \(sum\);

由于 \(x = ksum+r(mod \ sum)\)，在 \(pos\) 每移动一位，之后 \(x*10+i=ksum+10r+i(mod \ sum)\)，所以当前 \(r=10r+i(mod \ sum)\)

Code

    ll a[N];
    ll dp[20][180][180];

ll dfs(int pos, int mod, bool top, int res, int sum)
{
    if(! pos) return res == 0 && sum == mod;
    if(! top && dp[pos][sum][res] != -1) return dp[pos][sum][res]; 
    int up = 9;
    if(top) up = a[pos];
    ll ans = 0;
    for(int i = 0; i <= up && sum + i <= mod; i ++){
        ans += dfs(pos - 1, mod, top && i == up, (res * 10 + i) % mod, sum + i);
    }
    if(! top) dp[pos][sum][res] = ans;
    return ans;
}

int tot;
ll solve(ll x)
{
    tot = 0;
    while(x) a[++ tot] = x % 10, x /= 10;
    ll ans = 0;
    for(int i = 1; i <= 9 * tot; i ++){
        ms(dp, -1);
        ans += dfs(tot, i, 1, 0, 0);
    }
    return ans;
}

signed main()
{
    //IOS;
    ll l, r;
    while(~ sll2(l, r)){
        print(solve(r) - solve(l - 1), ‘\n‘);
    }
    return 0;
}