AtCoder Beginner Contest 336 E题 Digit Sum Divisible

标签：数位$dp$
题意：给定一个$n$，求小于等于$n$的数中有多少个能被自己的位数之和整除。（$1<=n<=10^{14}$）
**题解：**数位$dp$模版题，$dp[pos][sum][mod]$表示当第$pos$位各位数字之和为$sum$除原数的余数是$mod$且有没超出边界时候的个数。
代码：

#include <bits/stdc++.h>
using namespace std;typedef long long ll;
ll n, m, cnt = 0;
// dp[i][j][k]: 第i位 当前数字和为j 取模结果为k的个数
ll a[20], dp[20][10*20][10*20];ll dfs(ll pos, ll sum, ll mod, ll flag) {if (sum > m) return 0;if (pos == 0) return sum == m && mod == 0;if (!flag && dp[pos][sum][mod] != -1) return dp[pos][sum][mod];ll x = flag ? a[pos] : 9;ll ans = 0;for (ll i = 0; i <= x; i++) {ans += dfs(pos - 1, sum + i, (mod * 10 + i) % m, flag && (i == a[pos]));}if (!flag) dp[pos][sum][mod] = ans;return ans;
}int main() {cin >> n;while (n) {a[++cnt] = n % 10;n /= 10;}ll res = 0;for (int i = 1; i <= 9 * cnt; i++) {m = i;memset(dp, -1, sizeof(dp));res += dfs(cnt, 0, 0, 1);}cout << res;return 0;
}