Submission #1689360

---

Source Code Expand

#include <bits/stdc++.h>
#define ll long long
#define INF 1000000005
#define MOD 1000000007
#define EPS 1e-10
#define rep(i,n) for(int i=0;i<(int)(n);++i)
#define rrep(i,n) for(int i=(int)(n)-1;i>=0;--i)
#define srep(i,s,t) for(int i=(int)(s);i<(int)(t);++i)
#define each(a,b) for(auto (a): (b))
#define all(v) (v).begin(),(v).end()
#define len(v) (int)(v).size()
#define zip(v) sort(all(v)),v.erase(unique(all(v)),v.end())
#define fi first
#define se second
#define pb push_back
#define show(x) cout<<#x<<" = "<<(x)<<endl
#define spair(p) cout<<#p<<": "<<p.fi<<" "<<p.se<<endl
#define svec(v) cout<<#v<<":";rep(kbrni,v.size())cout<<" "<<v[kbrni];cout<<endl
#define sset(s) cout<<#s<<":";each(kbrni,s)cout<<" "<<kbrni;cout<<endl
#define smap(m) cout<<#m<<":";each(kbrni,m)cout<<" {"<<kbrni.first<<":"<<kbrni.second<<"}";cout<<endl

using namespace std;

typedef pair<int,int> P;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<double> vd;
typedef vector<P> vp;

const int MAX_N = 20;

ll dp[MAX_N][2];

vector<int> trans(ll ag)
{
    vector<int> vec;
    while(1){
        vec.pb(ag % 10);
        ag /= 10;
        if(ag == 0){
            break;
        }
    }
    reverse(all(vec));
    return vec;
}

ll solve(vi& vec)
{
    rep(i,20){
        rep(j,2){
            dp[i][j] = 0;
        }
    }
    dp[0][0] = 1;
    rep(i,len(vec)){
        rep(j,vec[i]){
            if(j != 4 && j != 9){
                dp[i+1][1] += dp[i][0];
                dp[i+1][1] += dp[i][1];
            }
        }
        if(vec[i] != 4 && vec[i] != 9){
            dp[i+1][0] += dp[i][0];
            dp[i+1][1] += dp[i][1];
        }
        for(int j=vec[i]+1;j<10;j++){
            if(j != 4 && j != 9){
                dp[i+1][1] += dp[i][1];
            }
        }
    }
    // show(dp[len(vec)][0]),show(dp[len(vec)][1]);
    return dp[len(vec)][0] + dp[len(vec)][1];
}

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll a,b;
    cin >> a >> b;
    vi u = trans(a-1);
    vi v = trans(b);
    cout << b-a+1 - (solve(v) - solve(u)) << endl;
    return 0;
}

Submission Info

Judge Result