洛谷 P4127 [AHOI2009]同类分布

题意简述

求l~r之间各位数字之和能整除原数的数的个数。

题解思路

数位DP

代码

#include <cstdio> #include <cstring> typedef long long ll; int cnt, C; int num[20]; ll l, r; ll dp[20][200][200]; ll dfs(int len, int sum, int rem, int mod, bool limit, ll s = 0) {if (!len) return sum == mod && rem == 0;ll& dp = ::dp[len][sum][rem];if (!limit && ~dp) return dp;int mx = limit ? num[len] : 9;for (register int i = 0; i <= mx; ++i)s += dfs(len - 1, sum + i, (rem * 10 + i) % mod, mod, limit && (i == mx));if (!limit) dp = s;return s; } ll solve(ll x, ll s = 0) {for (cnt = 0; x; num[++cnt] = x % 10, x = x / 10);C = cnt * 9;for (register int i = 1; i <= C; ++i){memset(dp, -1, sizeof dp);s += dfs(cnt, 0, 0, i, 1);}return s; } int main() {scanf("%lld%lld", &l, &r);printf("%lld\n", solve(r) - solve(l - 1)); }

转载于:https://www.cnblogs.com/xuyixuan/p/9925378.html

总结

以上是生活随笔为你收集整理的洛谷 P4127 [AHOI2009]同类分布的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。