joi6_too_long_code.c

#include<stdio.h>
#include<string.h>
char a[501],b[501];
int c,table[10][500][3][3][500][3];

int solve(int num,int mod,int big,int small,int keta,int zigzag){
	int res=0,i;
	if(table[num][mod][big][small][keta][zigzag]!=-1)return table[num][mod][big][small][keta][zigzag];		
	else if(keta>strlen(b))return table[num][mod][big][small][keta][zigzag]=0;                      
	else{
		if(big==1){
			if(num>b[keta-1]-'0')big=2;
			else if(num<b[keta-1]-'0')big=0;
		}
		if(small==1&&keta<=strlen(a)){
			if(num<a[keta-1]-'0')small=2;
			else if(num>a[keta-1]-'0')small=0;
		}
		for(i=0;i<10;i++){
			if((zigzag==1&&i<num)||(zigzag==-1&&i>num)){ 
				res+=solve(i,(i+10*mod)%c,big,small,keta+1,-zigzag);	
			}
			if(zigzag==0&&i<num){
				res+=solve(i,(i+10*mod)%c,big,small,keta+1,-1);
			}
			if(zigzag==0&&i>num){
				res+=solve(i,(i+10*mod)%c,big,small,keta+1,1);
			}
		}
		if(strlen(a)==strlen(b)){
			if(strlen(a)==keta&&small!=2&&big!=2&&mod==0){
				res++;
			}
		}
		else{
			if(keta==strlen(a)&&small!=2&&mod==0){res++;}
			else if(keta==strlen(b)&&big!=2&&mod==0){res++;}
			else if(keta>strlen(a)&&keta<strlen(b)&&mod==0)res++;
		}
		return 	table[num][mod][big][small][keta][zigzag]=res%10000;
	}
}	
	
int main(){                 
	scanf("%s%s%d",a,b,&c);
	int res=0,tt=1;
	memset(table,-1,sizeof(table));
	for(;tt<=9;tt++)res+=solve(tt,tt%c,1,1,1,0);
	printf("%d",res%10000);	
}