题目链接：HDOJ3967

题目：把【A，B】区间中的每个数X，分成左右两部分，如果和是K的倍数，那么算一个满足条件的数。求区间内的总数

分成左右两部分意思是说从任意一个数位断开，比如1234，可以分成1+234，也可以是12+34，还可以是123+4

如果有多种分解情况，算多种


然后就跟平衡数的思路一样了

平衡数是枚举支点，这个题就是枚举分隔的位置

如果X这个数有len位，那么枚举len-1个分界点，有一个符合就算一个

记忆化的写法就好，还是需要主要好10的次幂的打表与当前数位的位置要对应好


纠正以前理解数位DP中前导0的理解错误

在记忆化使用的时候可以不需要zero判断

但是在记录的时候需要

反应在代码中就是IF语句中的判断


#include<map>
#include<set>
#include<math.h>
#include<time.h>
#include<iostream>
#include<cstdio>
#include<queue>
#include<stack>
#include<stdio.h>
#include<cstring>
#include<string.h>
#include<algorithm>
#include<cstdlib>
using namespace std;

#define lson rt<<1,l,mid
#define rson rt<<1|1,mid+1,r
#define ll rt<<1
#define rr rt<<1|1
#define LL long long
#define ULL unsigned long long
#define maxn 1050
#define maxnum 1000050
#define eps 1e-6
#define input freopen("input.txt","r",stdin)
#define output freopen("output.txt","w",stdout)
#define MOD 1000000007

LL dp[20][50];
LL p[20];
int digit[20];
int K,sep;

LL dfs(int len,int divide,bool zero,bool flag){
	if (len==0) return divide==0; 
	if (flag&&dp[len][divide]!=-1) return dp[len][divide];
	int up=flag?9:digit[len];
	LL ret=0;
	for(int i=0;i<=up;i++){
		if (zero==0&&i==0&&len==sep+1) continue;
		ret+=dfs(len-1,(divide+(len>sep?i*p[len-sep-1]:i*p[len-1]))%K,zero||i,flag||i<up);
	}
	if (flag&&zero) dp[len][divide]=ret;
	return ret;
}

LL calc(LL x){
	if (x<=0) return 0;
	int len=0;
	while(x){
		digit[++len]=x%10;
		x/=10;
	}
	LL ret=0;
	for(int i=len-1;i>=1;i--){
		sep=i;
		memset(dp,-1,sizeof(dp));
		ret+=dfs(len,0,0,0);
	}
	return ret;
}

int main(){
	//input;
	p[0] = 1;  
    for(int i = 1; i < 20; ++i)  
        p[i] = p[i-1]*10;  
    LL A, B;
    while(~scanf("%I64d%I64d%d", &A, &B, &K))
        printf("%I64d\n", calc(B)-calc(A-1));
	return 0;
}