DEMSO - Đếm số
Tác giả: ladpro98
Ngôn ngữ: C++
#include <bits/stdc++.h>
#define long long long
const int N = 25;
using namespace std;
long A, B, D, K;
long F[N][N][N];
long DP(long a) {
int digit[N], d = 0;
while (a) {digit[++d] = a % 10; a /= 10;}
reverse(digit + 1, digit + 1 + d);
long res = 0;
for(int i = 1; i < d; i++) for(int j = 0; j <= 9; j++)
for(int k = 0; k <= K; k++) res += F[i][j][k];
long C[N][N][N][2];
memset(C, 0, sizeof C);
//C[i][j][k][t] = use i digits, last one is j, k bad position to the left,
//t == 1 if the number if == a up to i
for(int j = 1; j <= digit[1]; j++) C[1][j][0][j < digit[1] ? 0 : 1] = 1;
for(int i = 1; i <= d; i++) for(int j = 0; j <= 9; j++)
for(int k = 0; k <= K; k++) for(int t = 0; t <= 1; t++) {
if (t == 0) {
for(int next = 0; next <= 9; next++)
C[i + 1][next][abs(next - j) <= D ? k + 1 : k][0] += C[i][j][k][0];
}
else {
for(int next = 0; next <= digit[i + 1]; next++)
C[i + 1][next][abs(next - j) <= D ? k + 1 : k][next == digit[i + 1] ? 1 : 0] += C[i][j][k][t];
}
}
for(int j = 0; j <= 9; j++) for(int k = 0; k <= K; k++) for(int t = 0; t <= 1; t++)
res += C[d][j][k][t];
return res;
}
int main()
{
scanf("%lld %lld %lld %lld", &A, &B, &D, &K); K = min(K, 15ll);
//F[i][j][k] = use i digits, the last digit is j, and k bad position to the left
for(int j = 1; j <= 9; j++) F[1][j][0] = 1;
for(int i = 0; i <= 15; i++)
for(int j = 0; j <= 9; j++)
for(int k = 0; k <= K; k++)
for(int next = 0; next <= 9; next++)
if (abs(j - next) <= D) F[i + 1][next][k + 1] += F[i][j][k];
else F[i + 1][next][k] += F[i][j][k];
long res = DP(B) - DP(A - 1);
printf("%lld", res);
return 0;
}