记录编号	188050	评测结果	AAAAAAAAAA
题目名称	[NOIP 2013]计数问题	最终得分	100
用户昵称	Skyo	是否通过	通过
代码语言	C++	运行时间	0.005 s
提交时间	2015-09-21 19:40:57	内存使用	0.31 MiB

#include <cstdio>
#include <algorithm>
#include <cstring>
typedef long long L;
using namespace std;

L a, b, c, _10[15], ans[15], f[15][15][15];
bool flag;

void get_f(){
	_10[0] = 1;
	for(int i = 1; i < 15; i++) _10[i] = _10[i-1]*10;
	for(int i = 1; i < 10; i++) f[i][1][i] = 1;
	
	for(int i = 1; i < 10; i++)
	for(int j = 2; j < 15; j++){
		f[i][j][1] = _10[j-2]*(j-1);
		for(int k = 2; k < 10; k++)
			f[i][j][k] = f[i][j][1];
	}
	for(int i = 1; i < 10; i++)
	for(int j = 2; j < 15; j++){
		f[i][j][i] += _10[j-1];
	}
}

void get_all(){
	int la = 0, lb = 0;
	L ta = a-1, tb = b, all = 0;
	while(ta){
		la++, ta /= 10;
	}
	while(tb){
		lb++, tb /= 10;
	}
	for(int i = la; i < lb; i++){
		all += (_10[i]-_10[i-1])*i;
	}	all += (b-_10[lb-1]+1)*lb;
		all -= (a-_10[la-1])*la;
	ans[0] = all;
}

L d(L k, int i){
	if(!k) return 0;
	int fir, len = 0;
	L t = k, res = 0;
	while(t){
		len++, t /= 10;	
	}	fir = k / _10[len-1];
	if(len == 1) return i <= k;
	
	for(int j = 1; j < fir; j++){
		res += f[j][len][i];
	}
	res += d(k%_10[len-1], i) + d(_10[len-1]-1, i) + (fir==i)*(k%_10[len-1]+1);
	return res;
}

int main()
{
	freopen("count2013.in", "r", stdin);
	freopen("count2013.out", "w", stdout);
	scanf("%lld %lld", &b, &c);
	a = 1;
	get_f();
	get_all();
	for(int i = 1; i < 10; i++){
		ans[i] = d(b, i) - d(a-1, i);
		ans[0] -= ans[i];
	} 
	printf("%lld ", ans[c]);
	return 0;
}