bzoj1799 self 同类分布（数位dp）

迈不过友情╰ 2021-11-29 13:48 188阅读 0赞

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

## 分析：一个数的数字和是很小的，最大为9\*18，那么我们可以枚举这个数位和，因为这个数位和是要作模数的，只能枚举，所以dp的时候必须要加上这一维度才好递推。f\[i\]\[j\]\[k\]\[0/1\]表示到第i位数位和为j，在模sum意义下的余数为k，是否卡上界的数的个数。f\[0\]\[i\]\[j\]\[k\]表示前i位全都和原数x相等的数的个数（卡上界），f\[1\]\[i\]\[j\]\[k\]表示前i位至少有一位小于x相应数位的数的个数（不卡上界）。 ##

## 代码： ##

#include <cstring>
    #include <iostream>
    #define ll long long
    using namespace std;
    const int N = 200, L = 21;
    ll f[L][N][N][2];
    int n[L];
    
    ll calc(ll x, int P) {
    	if (!x) return 0;
    	memset(f, 0, sizeof(f));
    	int t = 0;
    	while (x) {
    		n[++t] = x % 10;
    		x /= 10;
    	}
    	f[t+1][0][0][0] = 1;
    	for (int i = t + 1; i > 1; i--)
    		for (int j = 0; j <= P; j++)
    			for (int k = 0; k < P; k++)
    				if (f[i][j][k][0] || f[i][j][k][1])///剪枝
    					for (int p = 0; p < 10; p++) {
    						int w = (10 * k + p) % P;
    						if (p < n[i-1] && j + p <= P) ///计算不卡上界的贡献
    							f[i-1][j+p][w][1] += f[i][j][k][0];
    						else if (p == n[i-1] && j + p <= P) ///计算卡上界的贡献
    							f[i-1][j+p][w][0] += f[i][j][k][0];
    						if (f[i][j][k][1] && j + p <= P) ///如果不卡上界 计算p>n[i-1]情况下的贡献
    							f[i-1][j+p][w][1] += f[i][j][k][1];
    					}
    	return f[1][P][0][0] + f[1][P][0][1];
    }
    
    int main() {
    	ll a, b, ans = 0;
    	cin >> a >> b;
    	for (int i = 1; i <= 9 * 18; i++)///枚举数位和i
    		ans += calc(b, i) - calc(a - 1, i);
    	cout << ans << endl;
    	return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，188人围观）

还没有评论，来说两句吧...

相关阅读

相关数位DP 详解

序 > 天堂在左，战士向右引言数位DP在竞赛中的出现几率极低，但是如果不会数位DP，一旦考到就只能暴力骗分。以下是数位DP详解，涉及到的例题有：

叁歲伎倆/ 2023年08月17日 17:38/ 0 赞/ 156 阅读

相关数位dp小结

数位dp小结关于limit的问题在数位dp中,limit的作用主要有两个。控制枚举的界限，倘若没有界限，每一位的枚举范围都是0-9. 但如果有界限，

桃扇骨/ 2023年07月03日 07:22/ 0 赞/ 33 阅读

相关数位dp总结

数位dp的题目一般问的是某个区间内满足某种性质的数的个数，而且对于数位dp的题目一般有都有比较通用的做法，在考虑问题的时候一般以树的形式来考虑： ![watermark_ty

「爱情、让人受尽委屈。」/ 2022年09月14日 03:06/ 0 赞/ 240 阅读

相关 BZOJ 3530 数数【AC自动机+数位dp】

[\[Sdoi2014\]数数][Sdoi2014] 简单数位dp+简单AC自动机反正数位DP是队友写的 AC自动机要记录两个值，一个是是否为一个串的结束，即不合法

骑猪看日落/ 2022年08月09日 01:53/ 0 赞/ 181 阅读

相关 Bomb（数位Dp）

Bomb Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 131072/65536 K (Java/Oth

布满荆棘的人生/ 2022年08月03日 00:09/ 0 赞/ 217 阅读

相关数位DP

Problem Description 据说，QAQ 的幸运数字是含有 "47" （4 和 7 相邻）的数，例如 47, 147, 247, 470, 471, 2047

小灰灰/ 2022年06月15日 00:40/ 0 赞/ 326 阅读

相关 BZOJ 3209 数位dp（求单个phi值模板）

[传送门][Link 1] 题意是求![\\prod\_\{i=1\}^\{n\} biultin popcount(i)][prod_i_1_n_ biultin popc

朴灿烈づ我的快乐病毒、/ 2022年05月15日 07:05/ 0 赞/ 157 阅读

相关 poj3252（数位dp）

题目链接：https://vjudge.net/problem/POJ-3252 题意：求\[l,r\]之间的Round Number数，RN数即化为二进制后0的个数不少于1

素颜马尾好姑娘i/ 2021年12月21日 01:03/ 0 赞/ 325 阅读

相关 bzoj1799 self 同类分布（数位dp）

题意：给出a,b，求出\[a,b\]中各位数字之和能整除原数的数的个数。分析：一个数的数字和是很小的，最大为9\18，那么我们可以枚举这个数位和，因为这个数位和是要作

迈不过友情╰/ 2021年11月29日 13:48/ 0 赞/ 189 阅读

相关数位DP模板

int a[20]; ll dp[20][state]; ll dfs(int pos,/state变量/,bool lead/前导零/,bool li

左手的ㄟ右手/ 2021年09月19日 05:42/ 0 赞/ 386 阅读