HYSBZ 1799 self 同类分布——数位dp

HYSBZ 1799 self 同类分布——数位dp

题意：给出a,b，求出[a,b]中各位数字之和能整除原数的数的个数。

思路：给出a,b，求出[a,b]中各位数字之和能整除原数的数的个数。1<=a<=b<=1e18. 注意到各位数字之和最大是153.考虑枚举这个东西。那么需要统计的是[0,a-1]和[0,b]内各位数字之和为x且能整除x的数字个数。 那么我们只需要数位dp一波即可。 令dp[pos][i][x]表示有pos位且数字之和为x的数mod P=i的数字个数。

则转移方程显然可得

#include #include #include #include using namespace std;typedef long long ll;int num[20];ll dp[20][200][200];ll dfs(int t, int pos, int sum, int mod, bool limit, bool lead) { if (pos == 0) return (sum==t && mod==0); if (!limit && !lead && ~dp[pos][sum][mod]) return dp[pos][sum][mod]; int up = limit ? num[pos] : 9; ll ans = 0; for (int i = 0; i <= up; i++) { ans += dfs(t, pos-1, sum + i, (10%t*mod+i)%t, limit && i==num[pos], lead && i==0); } if (!limit && !lead) dp[pos][sum][mod] = ans; return ans;}ll solve(ll n) { if (n < 0) return 0; int pos = 0; while (n) { num[++pos] = n % 10; n /= 10; } ll ans = 0; for (int i = 1; i <= pos*9; i++) { memset(dp, -1, sizeof(dp)); ans += dfs(i, pos, 0, 0, true, true); } return ans;}int main() { ll x, y; scanf("%lld%lld", &x, &y); printf("%lld\n", solve(y) - solve(x-1)); return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。