DEMSO - Đếm số
Tác giả: happyboy99x
Ngôn ngữ: C++
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long int64;
const int L = 20;
int64 f[L][L][10][2];
int lg10(int64 n) {
int res = 0;
while(n) n /= 10, ++res;
return res;
}
int64 calc(int64 n, int64 d, int64 k) {
if(n < 10) return n;
memset(f, 0, sizeof f);
int len = lg10(n);
k = min(k, len-1LL);
for(int v = 0; v < 10; ++v)
for(int diff = 0; diff <= k; ++diff) {
f[len-1][diff][v][1] = 1;
f[len-1][diff][v][0] = v == n % 10 ? 1 : 0;
}
int64 num = n;
for(int i = len-2; i >= 0; --i, num /= 10)
for(int diff = 0; diff <= k; ++diff)
for(int v = 0; v < 10; ++v) if(i | v)
for(int s = 0; s < 2; ++s)
for(int nx = 0; nx <= (s == 0 ? num % 10 : 9); ++nx)
f[i][diff][v][s] += f[i+1][diff + (abs(nx - v) <= d ? 1 : 0)][nx][s | (nx < num % 10 ? 1 : 0)];
int64 res = 0;
for(int s = 1; s <= num; ++s)
res += f[0][0][s][s < num ? 1 : 0];
return res;
}
int64 beautiful(int64 n, int64 d, int64 k) {
int64 res = calc(n, d, k);
for(int64 t = 10; t <= n; t *= 10)
res += calc(t-1, d, k);
return res;
}
int main() {
int64 a, b, d, k;
cin >> a >> b >> d >> k;
cout << beautiful(b, d, k) - beautiful(a-1, d, k) << endl;
return 0;
}