文件详细信息

下载本文件

本文件的大小为 1175 字节。

#include<cstdio>
#include<cstring>
template<typename T>
void read(T&num){
	int ch=getchar();
	num=0;
	while(ch<48||ch>57)ch=getchar();
	while(ch>=48&&ch<=57)num=(num<<3)+(num<<1)+(ch^48),ch=getchar();
}
template<typename T>
void write(T a){
	static int ch[20],cnt=0;
	if(a==0)putchar('0');
	while(a)ch[cnt++]=a%10|48,a/=10;
	while(cnt)putchar(ch[--cnt]);
}
typedef long long ll;
const int maxk=1000;
ll l,r,k;
int x,dl[20],dr[20];
void init(int*arr,ll num){
	while(num){
		arr[++x]=num%10;
		num/=10;
	}
	x=0;
}
struct Data{
	ll a;
	int b;
}f[19][170][maxk+1];
void merge(Data&x,const Data y){
	x.a+=y.a;
	x.b=y.b;
}
Data dfs(int cur,int sum,int rem,bool lim1,bool lim2){
	if(!lim1&&!lim2&&f[cur][sum][rem].a!=-1ll)return f[cur][sum][rem];
	Data ans=Data{0,rem};
	if(!cur){
		if(sum+rem>=k)ans=Data{1,0};
		else ans=Data{0,sum+rem};
	}else{
		int d1=lim1?dl[cur]:0,d2=lim2?dr[cur]:9;
		for(int i=d1;i<=d2;i++)merge(ans,dfs(cur-1,sum+i,rem,lim1&&(i==d1),lim2&&(i==d2)));
	}
	if(!lim1&&!lim2)f[cur][sum][rem]=ans;
	return ans;
}
int main(){
	read(l),read(r),read(k);
	init(dl,l);
	init(dr,r);
	memset(f,-1,sizeof(f));
	write(dfs(18,0,0,true,true).a),putchar('\n');
	return 0;
}