标签：填满 int lim 枚举 整数 满足 位数 dp 数位
见题：E - Digit Sum Divisible (atcoder.jp)
P4127 [AHOI2009] 同类分布 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
考虑数位动规，设方程 $dp[i][j][k][l]$ 为状态:
$i$：搜到了第 $i$ 位（倒着枚举，也就是指 $i$ 到最高位都填完了）。
$j$: 表示当前的数位总和
$k$: 表示当前的数位总和模上我们枚举的数位和
$l$: 是否 $i$ 前面的位（包括 $i$）都填满了。这里的填满指填的与原数 $n$ 相同。例如 $114514$ 就是在 $n = 119198$ 时第五到最高位的填满。
那么状态转移方程就是：对于ｌ＝０，也就是当前位前面的没有被填满，那么我们在这个位置可以枚举到９
$f_{i, 0, k, l} = \sum\limits_{t = 0}^9 f_{i - 1,j + t, (10k + t) \bmod m, 0}$。表示枚举第 $i$ 位填的数为 $t$。那么因为前面存在某一位没填满，那么后面的位 $0 \sim 9$ 都是可以填的。因此 $t$ 的范围为 $[0, 9]$。
$f_{i, 1, k, l} = \sum\limits_{t = 0}^pf_{i - 1, j + t, (10k + t) \bmod m, [t == p]}$，其中 $p$ 表示给定的 $n$ 的第 $i$ 位，$[t = p]$ 表示 $t$ 是否等于 $p$（真为 $1$，假为 $0$）。表示枚举的第 $i$ 位为 $t$。那么因为前面每一位都填满了，那么这一位肯定不能超过 $n$ 原来的这一位，所以枚举到 $p$.
```
#include
#define int long long
using namespace std;
const int N = 1e6 + 10, mod = 1e9 + 7;
int dp[20][300][300][2], dep[20];
int dfs(int u, int s, int x, int k, int lim)
{
if (u == 0)
return s == k && x == 0;
if (dp[u][s][x][lim] != -1)
return dp[u][s][x][lim];
int ed = lim ? dep[u] : 9;
dp[u][s][x][lim] = 0;
for (int i = 0; i <= ed; i++)
dp[u][s][x][lim] += dfs(u - 1, s + i, (x * 10 + i) % k, k, lim && (i == ed));
return dp[u][s][x][lim];
}
signed main()
{
std::ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int a, b;
cin >> a >> b;
int len = 0;
a--;
while (a)
dep[++len] = a % 10, a /= 10;
int res = 0;
for (int i = 1; i <= 9 * 18; i++)
{
memset(dp, -1, sizeof dp);
res += dfs(len, 0, 0, i, 1);
}
len = 0;
while (b)
dep[++len] = b % 10, b /= 10;
int ans = 0;
for (int i = 1; i <= 9 * 18; i++)
{
memset(dp, -1, sizeof dp);
ans += dfs(len, 0, 0, i, 1);
}
cout << ans - res;
return 0;
}
```
标签：填满,
int,
lim,
枚举,
整数,
满足,
位数,
dp,
数位
From： https://www.cnblogs.com/o-Sakurajimamai-o/p/18213472