「Bzoj 1799」「Ahoi2009」同类分布 (数位DP)

BZOJ 1799
题意：给出$a,b$，求出$[a,b]$中各位数字之和能整除原数的数的个数。
设$dp(a,i,j)$为前$a$位数字和为$i$，数模上数字和值为$j$的个数。
枚举数字和，然后求即可。转移方程

$$
dp(a,i,j)+=dp(a-1,i+p,(j+p)\% mod)
$$

其中$mod$为枚举的数字和，$p$为$a$位上枚举填的数。

#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<set>
#include<queue>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define fir first
#define sec second
#define mp make_pair
using namespace std;

namespace flyinthesky {

    LL A, B, len, b[25], MOD, dp[25][170][170], cf[100];

    LL dfs(LL a, LL sum, LL gg, LL p, LL limit) {
        if (a == 0) {
            if (!sum) return 0ll;
            if (gg % sum == 0 && sum == MOD) return 1ll;
            return 0ll;
        }
        if (!limit && p != -233 && dp[a][sum][gg % MOD] >= 0) return dp[a][sum][gg % MOD];
        LL ed = (limit ? b[a] : 9), ret = 0;
        for (LL i = 0; i <= ed; ++i) {
            if (i == 0 && p == -233) ret += dfs(a - 1, 0, 0, -233, (limit && (ed == i)));
            else ret += dfs(a - 1, sum + i, gg + i * cf[a - 1], i, (limit && (ed == i)));
        }
        if (!limit && p != -233) dp[a][sum][gg % MOD] = ret;
        return ret;
    }
    LL getans(LL x) {
        LL ret = 0;
        len = 0; while (x) b[++len] = x % 10, x /= 10;
        for (MOD = 1; MOD <= 9 * len; ++MOD) {
            ms(dp, -1);
            ret += dfs(len, 0, 0, -233, 1);
        }
        return ret;
    }

    void clean() {
    }
    int solve() {
        clean();
        cf[0] = 1ll;
        for (LL i = 1; i <= 100; ++i) cf[i] = cf[i - 1] * 10ll;
        cin >> A >> B;
        cout << getans(B) - getans(A - 1) << endl;
        return 0; 
    }
}
int main() {
    flyinthesky::solve();
    return 0;
}