Submission #2200999

---

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;
ll solve(string s){
    int sl=s.length();
    ll dp[510][510][11][3][2]={};
    int b=s[0]-'0';
    for(int k=0;k<10;k++){
        for(int l=0;l<2;l++){
            int n=0;
            if(k==b){
                n=1;
            }else if(k>b){
                continue;
            }
            dp[1][k%m][k][l][n]=1;
        }
    }
  	if(sl==1){
    	return b/m;
    }
    for(int i=1;i<sl;i++){ //今見ている桁
        b=s[i]-'0';
        for(int o=1;o<10;o++){
            if(i==sl-1){
                (dp[i+1][o%m][o][1][0]+=1)%=MOD;
                continue;
            }
			for(int l=0;l<2;l++){
                (dp[i+1][o%m][o][l][0]+=1)%=MOD;
            }
        }
        for(int j=0;j<m;j++){ //ここまでをmで割った余り
            for(int k=0;k<10;k++){ //今見ている桁の数
                for(int l=0;l<2;l++){ //増減
                    for(int n=0;n<2;n++){ //一致?
                        for(int o=0;o<10;o++){//次の桁の数
                            if(l==0){
                                if(o>=k){
                                    continue;
                                }
                            }else if(l==1){
                                if(o<=k){
                                    continue;
                                }
                            }
                            if(n){
                                if(o==b){
                                    (dp[i+1][(j*10+o)%m][o][!l][n]+=dp[i][j][k][l][n])%=MOD;
                                }else if(o<b){
                                    (dp[i+1][(j*10+o)%m][o][!l][!n]+=dp[i][j][k][l][n])%=MOD;
                                }
                            }else{
                                (dp[i+1][(j*10+o)%m][o][!l][n]+=dp[i][j][k][l][n])%=MOD;
                            }
                        }
                    }
                }
            }
        }
    }
    ll ret=0;
    for(int k=0;k<10;k++){
        for(int l=0;l<2;l++){
            for(int n=0;n<2;n++){
                (ret+=dp[sl][0][k][l][n])%=MOD;
              cout<<k<<" "<<l<<" "<<n<<" "<<dp[sl][0][k][l][n]<<endl;
            }
        }
    }
    return ret-1;
}
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;
    cout<<solve(b)-solve(b)<<endl;
    return 0;
}

Submission Info

Judge Result