Submission #1295207

#TimeUsernameProblemLanguageResultExecution timeMemory
1295207al95ireyizPalindrome-Free Numbers (BOI13_numbers)C++20
100 / 100
2 ms584 KiB
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define vll vector<ll>
#define len(x) (ll)x.size()
const ll INF = 1e9, INFL = 1e18;
const ll MOD = 1e9 + 7;
const ll maxn = 3e5 + 5;
 
ll n, m, k = 0;

vll v;
ll dp[20][10][10][5][2];
#define dpp dp[x][e1][e2][st][tg]
ll dfs(ll x, ll e1, ll e2, ll st, ll tg){
    if(x == len(v)) return 1;
    if(dpp != -1) return dpp;
    dpp = 0;
    ll lm = 9;
    if(tg) lm = v[x];
    for(ll i = 0; i <= lm; i ++){
        if(st == 1){
            if(i == e1) continue;
        }
        if(st == 2){
            if(i == e1 or i == e2) continue;
        }
        if(st == 0){
            if(i != 0) dpp += dfs(x + 1, i, e1, 1, (tg & (i == lm)));
            else dpp += dfs(x + 1, 0, 0, 0, (tg & (i == lm)));
        }
        else{
            dpp += dfs(x + 1, i, e1, min(2ll, st + 1), (tg & (i == lm)));
        }
    }
    return dpp;
}
ll get(ll x){
    if(x == -1) return 0;
    if(x == 0) return 1;
    memset(dp, -1, sizeof(dp));

    v.clear();
    while(x){
        v.push_back(x % 10);
        x /= 10;
    }
    reverse(v.begin(), v.end());
    return dfs(0, 0, 0, 0, 1);
}
void _() {
    cin >> n >> m;
    // eger 1-den boyuk palindromic hissesi olanlari axtaririqsa, ele onda 2 ve 3 palindromic hissesi olanlari tapsaq bes edir.
    cout << get(m) - get(n - 1) << '\n';
}
signed main() {
    cin.tie(0)->sync_with_stdio(0);
    ll t = 1;
    // cin >> t;
    while(t --) _();
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...