DEMSO - Đếm số
Tác giả: skyvn97
Ngôn ngữ: C++
#include<cstdio>
#include<cstring>
typedef long long ll;
struct num {
int nd;
int d[20];
num() {
nd=0;
}
num(ll x) {
nd=0;
while (x>0) {
nd++;
d[nd-1]=x%10;
x=x/10;
}
}
int operator [] (const int &i) const {
return (d[i]);
}
};
ll num9[20];
ll f[20][13][20][3];
ll a,b;
int d,k;
int abs(const int &x) {
if (x<0) return (-x); else return (x);
}
void init(void) {
int i;
num9[1]=9;
for (i=2;i<=17;i=i+1) num9[i]=(num9[i-1]+1)*10-1;
}
ll count(const ll &x,int m) {
if (x<1) return (0);
num tmp=num(x);
int n=tmp.nd;
//printf("%d\n",n);
if (m>=n) m=n-1;
int i,j,k,l,t;
for (i=1;i<17;i=i+1)
for (j=0;j<10;j=j+1)
for (k=0;k<17;k=k+1)
for (l=0;l<2;l=l+1)
f[i][j][k][l]=0;
for (i=1;i<=tmp[n-1];i=i+1) f[1][i][0][i<tmp[n-1]]=1;
for (i=1;i<n;i=i+1)
for (j=0;j<10;j=j+1)
for (k=0;k<i && k<=m;k=k+1)
for (l=0;l<2;l=l+1)
for (t=0;t<=(1-l)*tmp[n-i-1]+9*l;t=t+1) {
f[i+1][t][k+(abs(t-j)<=d)][l||(t<tmp[n-i-1])]+=f[i][j][k][l];
//printf("Updated f(%d,%d,%d,%d)=%lld to f(%d,%d,%d,%d)\n",i,j,k,l,f[i][j][k][l],i+1,t,k+(abs(t-j)<=d),l||(t<tmp[n-i-1]));
}
ll res=0;
for (j=0;j<10;j=j+1)
for (k=0;k<=m;k=k+1)
res+=f[n][j][k][1]+f[n][j][k][0];
//printf("Result is %lld\n",res);
return (res);
}
ll count(const ll &x) {
int i;
if (x<1) return (0);
//printf("Count %lld\n",x);
int n=num(x).nd;
ll res=0;
for (i=1;i<n;i=i+1) {
res+=count(num9[i],k);
//printf("%lld\n",res);
}
res+=count(x,k);
return (res);
}
void process(void) {
scanf("%lld",&a);
scanf("%lld",&b);
scanf("%d",&d);
scanf("%d",&k);
printf("%lld",count(b)-count(a-1));
}
int main(void) {
init();
process();
return 0;
}