Submission #2202354

---

Source Code Expand

#include<vector>
#include<iostream>
#include<string>
#include<algorithm>
#include<math.h>
#include<map>
#include<functional>
#include<queue>
#include<stack>
#include<string.h>
#include<list>
#include<limits>
#include<bitset>
#include<ctype.h>
#include<set>
using namespace std;
typedef long long int ll;
typedef pair<int,int> P;
const ll MOD=10000;
const ll INF=1000000000;
const int MAX=100001;
const double EPS=1e-10;
int m;
int dp[510][500][10][3][2];//見ている場所、余り、直前の数値、ジグザグ、同じか
    
int solve(string s,int a,int b,int c,int d,int e){
    int sl=s.length();
    int sa=s[a]-'0';
  	if(a==sl){
		if(b==0){
			return 1;
        }else{
			return 0;
        }
    }
    if(dp[a][b][c][d][e]!=-1){
        return dp[a][b][c][d][e];
    }
    int ret=0;
    int l;
    if(e){
        l=sa;
    }else{
        l=9;
    }
    for(int i=0;i<=l;i++){
        if(d==0&&i>=c){
            continue;
        }
        if(d==1&&i<=c){
            continue;
        }
        int et=0;
        if(e&&(sa==i)){
            et=1;
        }
        if(d==2){
            if(c!=0&&c==i){
                continue;
            }
            if(c==0){
                ret+=solve(s,a+1,(b*10+i)%m,i,2,et);
            }else if(c>i){
                ret+=solve(s,a+1,(b*10+i)%m,i,1,et);
            }else{
                ret+=solve(s,a+1,(b*10+i)%m,i,0,et);
            }
        }else{
            ret+=solve(s,a+1,(b*10+i)%m,i,!d,et);
        }
    }
    ret%=MOD;
    return dp[a][b][c][d][e]=ret;
}
int main(){
    string a,b;
    cin>>a;
    int aa=a[a.length()-1]-'0';
    if(aa==0){
		for(int i=a.length()-1;i>=1;i--){
          	aa=a[i]-'0';
          	if(aa==0){
              	a[i]='9';
				int aaa=a[i-1]-'0';
              	if(aaa==0){
					continue;
                }
              	aaa--;
              	a[i-1]='0'+aaa;
            }else{
				break;
            }
        }
    }else{
        aa--;
        a[a.length()-1]='0'+aa;
    }
  	if(a[0]=='0'){
		a.erase(a.begin());
    }
    cin>>b;  
    cin>>m;
    memset(dp,-1,sizeof(dp));
    int ansa=solve(a,0,0,0,2,1)%MOD;
  	memset(dp,-1,sizeof(dp));
    int ansb=solve(b,0,0,0,2,1)%MOD;
    cout<<(ansb-ansa+MOD)%MOD<<endl;
    return 0;
}

Submission Info

Judge Result