k-balance.cpp

#include<map>
#include<set>
#include<ctime>
#include<cmath>
#include<queue>
#include<stack>
#include<bitset>
#include<vector>
#include<cstdio>
#include<string>
#include<cassert>
#include<cstring>
#include<numeric>
#include<sstream>
#include<iterator>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long LL;
#define MM(a,x) memset(a, x, sizeof(a))
#define P(x) cout<<#x<<" = "<<x<<endl;
#define P2(x,y) cout<<#x<<" = "<<x<<", "<<#y<<" = "<<y<<endl;
#define PV(a,n) for(int i=0;i<n;i++) cout<<#a<<"[" << i <<"] = "<<a[i]<<endl;
#define TM(a,b) cout<<#a<<"->"<<#b<<": "<<1.*(b-a)/CLOCKS_PER_SEC<<"s\n";

const LL MD = LL(1e9) + 7;

LL ten[51];
LL p10[51];
LL h(LL m);

LL brute(LL L, LL R, int k) {
	LL ret = 0;
	for(int i = L; i <= R; i++) {
		int s[100], ct;
		if(i % 100000000 == 0) P(i);
		LL T = i;
		ct = 0;
		while(T) {
			s[ct++] = T % 10;
			T /= 10;
		}
		if(ct < k) {ret += i; continue;}
		int sL = 0, sR = 0;
		for(int j = 0; j < k; j++) {
			sL += s[j];
			sR += s[ct - j - 1];
		}
		if(sL == sR)
			ret = (ret + i) % MD;
	}
	return ret % MD;
}

vector<int> toD(LL n) {
	vector<int> r;
	while(n) {
		r.push_back(n % 10);
		n /= 10;
	}
	reverse(r.begin(), r.end());
	return r;
}

LL h(LL m) {
	LL L = 1, R = LL(pow(10., (int)m) + 0.5) - 1;
	LL t1 = L + R;
	LL n = R - L + 1;
	if(t1 % 2 == 0) t1 /= 2;
	else if(n % 2 == 0) n /= 2;
	t1 %= MD;
	n %= MD;
	LL ret = t1 * n % MD;
	return ret;
}


LL g(int cur, int sz, int p[], int k, bool allZero) {
//	PV(p, sz);
//	P(cur);
	LL ret = 0;
	int pZero = 0;
	for(int i = 0; i < cur; i++) {
		if(p[i] == 0) {
			pZero = i + 1;
		} else {
			break;
		}
	}

	vector<int> d;
	for(int i = pZero; i < cur; i++) d.push_back(p[i]);
	sz -= pZero;

	int nsure = d.size(), L, R, M;

	if(sz <= k) {
		LL sure = 0;
		for(int i = 0; i < nsure; i++) {
			sure = (10 * sure + d[i]) % MD;
		}
		int nosure = sz - nsure;
		int minus = allZero && (nosure > 0);
		ret = (h(nosure) - minus * h(nosure - 1) % MD + (ten[nosure] - minus * ten[nosure - 1]) % MD * ten[nosure] % MD * sure % MD) % MD;
		if(ret < 0) ret += MD;
		return ret;
	}

	if(2 * k <= sz) {
		M = sz - 2 * k, L = R = k;
	} else {
		M = 2 * k - sz, L = R = sz - k;
	}

	LL dL[10][100] = {};
	LL X[10][100] = {};
	X[0][0] = 1;
	for(int i = 1; i <= 9; i++) {
		int st = (i == 1 && allZero) ? 1 : 0;
		for(int j = 0; j < 100; j++) {
			for(int l = st; l <= 9 && l <= j; l++) {
				X[i][j] += X[i - 1][j - l];
			}
			X[i][j] %= MD;
		}
	}

	LL dR[10][100] = {};
	LL Y[10][100] = {};
	Y[0][0] = 1;
	for(int i = 1; i <= 9; i++) {
		for(int j = 0; j < 100; j++) {
			for(int l = 0; l <= 9 && l <= j; l++) {
				Y[i][j] += Y[i - 1][j - l];
			}
			Y[i][j] %= MD;
		}
	}

	for(int i = 1; i <= 9; i++)
		for(int j = 0; j < 100; j++) {
			for(int x = i - 1; x >= 0; x--) {
				for(int y = (allZero && x == i - 1); y <= 9 && y <= j; y++) {
					if(x != i - 1)
						dL[i][j] += X[i - 1][j - y] * y % MD * ten[x] % MD;
					else
						dL[i][j] += Y[i - 1][j - y] * y % MD * ten[x] % MD;
				}
			}
			dL[i][j] %= MD;
		}
	for(int i = 1; i <= 9; i++)
		for(int j = 0; j < 100; j++) {
			for(int x = i - 1; x >= 0; x--) {
				for(int y = 0; y <= 9 && y <= j; y++) {
					dR[i][j] += Y[i - 1][j - y] * y % MD * ten[x] % MD;
				}
			}
			dR[i][j] %= MD;
		}
	if(nsure < L) {
		//	cout << "1)" << endl;
		int nL = L - nsure;
		int sL = 0;
		LL sure = 0;
		for(int i = 0; i < nsure; i++) {
			sure = (10 * sure + d[i]) % MD;
			sL += d[i];
		}

		for(int ds = 0; ds + sL < 100; ds++) {
			LL cL = ten[M] * Y[R][ds + sL] % MD;
			LL vL = (dL[nL][ds] + X[nL][ds] * sure % MD * ten[nL]) % MD * ten[M + R] % MD;
			ret += cL * vL % MD;

			LL cM = X[nL][ds] * Y[R][ds + sL] % MD;
			LL vM = h(M) * ten[R] % MD;
			ret += cM * vM % MD;

			LL cR = X[nL][ds] * ten[M];
			LL vR = dR[R][ds + sL];
			ret += cR * vR % MD;
		}
		ret %= MD;
	} else if(nsure <= L + M) {
		//	cout << "2)" << endl;
		int sL = 0;
		int nM = L + M - nsure;
		LL vL = 0, vM = 0;
		for(int i = 0; i < L; i++) {
			sL += d[i];
			vL = (10 * vL + d[i]) % MD;
		}
		for(int i = L; i < nsure; i++) {
			vM = (10 * vM + d[i]) % MD;
		}

		LL cL = ten[nM] * Y[R][sL] % MD;
		vL = vL * ten[M + R] % MD;
		ret += cL * vL % MD;

		LL cM = Y[R][sL] % MD;
		vM = vM * ten[nM] % MD;
		vM = (h(nM) + vM * ten[nM]) % MD * ten[R] % MD;
		ret += cM * vM % MD;

		LL cR = ten[nM];
		LL vR = dR[R][sL];
		ret += cR * vR % MD;
		ret %= MD;
	} else {
		//	cout << "3)" << endl;
		LL sure = 0;
		int sL = 0, sR = 0;
		for(int i = 0; i < L; i++) sL += d[i];
		for(int i = L + M; i < nsure; i++) sR += d[i];
		for(int i = 0; i < nsure; i++) sure = (10 * sure + d[i]) % MD;

		int nR = R - (nsure - (L + M));
		if(sL >= sR) {
			LL cR = Y[nR][sL - sR];
			LL vR = dR[nR][sL - sR];
			ret += (vR + sure * ten[nR] % MD * cR) % MD;
			ret %= MD;
		}
	}
	//P(ret);
	//cout << endl;
	return ret;
}

void dfs(int cur, vector<int>& D, int p[], int k, bool isEqual, bool allZero, LL & r) {
	int sz = (int) D.size();
	if(cur == sz) {
		if(isEqual)	return;
		else r += g(cur, D.size(), p, k, allZero);
		return;
	}
	if(isEqual) {
		for(int i = 0; i <= D[cur]; i++) {
			p[cur] = i;
			dfs(cur + 1, D, p, k, i == D[cur], allZero && (i == 0), r);
		}
	} else {
		if(allZero) {
			for(int i = cur; i < D.size(); i++) {
				r += g(i, D.size(), p, k, 1);
				p[i] = 0;
			}
		} else {
			r += g(cur, D.size(), p, k, 0);
		}
	}
}

//1,2,...,n
LL f(LL n, LL k) {
	vector<int> D = toD(n);
	LL r = 0;
	int p[50] = {};
	dfs(0, D, p, k, 1, 1, r);
	r %= MD;
	return r;
}

int main() {
	p10[0] = ten[0] = 1;
	for(int i = 1; i < 50; i++) {
		p10[i] = 10 * p10[i - 1];
		ten[i] = 10 * ten[i - 1] % MD;
	}
	LL L, R, k;
	cin >> L >> R >> k;
	assert(L <= R && R < LL(1e18));
	LL rL = f(L, k);
	LL rR = f(R + 1, k);
//	P(rL);
//	P(rR);
	LL r = (rR - rL + MD) % MD;
	cout << r << endl;
	//P(brute(L, R, k));
	return 0;
}