Submission #1345705

#TimeUsernameProblemLanguageResultExecution timeMemory
1345705iamhereforfunPalindrome-Free Numbers (BOI13_numbers)C++20
72.50 / 100
0 ms344 KiB
// Starcraft 2 enjoyer //

#include <bits/stdc++.h>

// #pragma GCC target("avx2")
// #pragma GCC optimize("O3")
// #pragma GCC optimize("unroll-loops")

using namespace std;

#define LSOne(X) ((X) & -(X))

const int N = 4e5 + 5;
const int M = 1e6 + 5;
const int K = 19;
const int LG = 21;
const long long INF = 1e18 + 5;
const int C = 26;
const int B = 1000;
const int MOD = 998244353;

long long dp[19][11][11][2]; // dp[pos][secondlast][last][greater]
long long a, b;
string cur;

long long cal(int p, int sl, int l, bool smaller)
{
    if (p < 0)
        return 1;
    if (dp[p][sl][l][smaller] != -1)
        return dp[p][sl][l][smaller];
    int i = smaller ? 9 : cur[p] - '0';
    long long ans = 0;
    for (int x = 0; x <= i; x++)
    {
        if (x == 0 && l == -1)
        {
            ans += cal(p - 1, 10, 10, smaller);
        }
        else
        {
            if (x == l || x == sl)
                continue;
            int ns = smaller | (x != i);
            ans += cal(p - 1, l, x, ns);
        }
    }
    return dp[p][sl][l][smaller] = ans;
}

long long get(long long a)
{
    cur = to_string(a);
    memset(dp, -1, sizeof(dp));
    reverse(cur.begin(), cur.end());
    return cal(cur.size() - 1, 10, 10, 0);
}

inline void solve()
{
    cin >> a >> b;
    cout << get(b) - get(a - 1) << "\n";
}

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    // cin >> t;
    for (int x = 1; x <= t; x++)
    {
        solve();
    }
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...