「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;
}

------ 本文结束 ------