Submission #1771762

---

Source Code Expand

#include<bits/stdc++.h>
#define REP(i,n) for(int i=0;i<n;i++)
#define LOOP(i,x,n) for(int i=x;i<n;i++)
#define ALL(v) (v).begin(),(v).end()
#define PB push_back
#define MP make_pair
#define FIR first
#define SEC second
#define int long long
using namespace std;
const int MOD=1000000007;
const int INF=1000000009;

int DP(string s){
  int len=s.size();
  int dp[len+1][2][2]={};
  dp[0][0][0]=1;

  REP(i,len)REP(j,2)REP(k,2){
    int lim=(j==0?s[i]-'0':9);
    REP(l,lim+1){
      if(j==1||l<lim){
        if(k==1||l==4||l==9)dp[i+1][1][1]+=dp[i][j][k];
        else dp[i+1][1][0]+=dp[i][j][k];
      }else{
        if(k==1||l==4||l==9)dp[i+1][0][1]+=dp[i][j][k];
        else dp[i+1][0][0]+=dp[i][j][k];
      }
    }
  }
  return dp[len][0][1]+dp[len][1][1];
}

signed main(){
  int a,b;
  cin>>a>>b;
  cout<<DP(to_string(b))-DP(to_string(a-1))<<endl;
  return 0;
}

Submission Info

Judge Result