Submission #1254586

#TimeUsernameProblemLanguageResultExecution timeMemory
1254586XXBabaProBerkayPalindrome-Free Numbers (BOI13_numbers)C++20
100 / 100
1 ms328 KiB
#include <bits/stdc++.h> using namespace std; #define F first #define S second #define MP make_pair #define PB push_back using ll = long long; using ld = long double; using pi = pair<int, int>; using pll = pair<ll, ll>; template<typename T> using vec = vector<T>; template<typename T, int N> using arr = array<T, N>; ll gcd(ll a, ll b) { return b == 0 ? a : gcd(b, a % b); } ll lcm(ll a, ll b) { return a * b / gcd(a, b); } const ll INF = 1e18; const int MOD = 998244353; vec<int> num; ll dp[2][3][10][10][20]; ll solve(bool f, int g, int d1, int d2, int i) { if (i >= (int)num.size()) return 1; g = min(g, 2); if (dp[f][g][d1][d2][i] != -1) return dp[f][g][d1][d2][i]; dp[f][g][d1][d2][i] = 0; for (int j = 0; j <= (f ? 9 : num[i]); j++) { if ((g >= 2 && j == d2) || (g >= 1 && j == d1)) continue; dp[f][g][d1][d2][i] += solve(f || j < num[i], g + (g > 0 || j > 0), j, d1, i + 1); } return dp[f][g][d1][d2][i]; } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); memset(dp, -1ll, sizeof dp); ll a, b; cin >> a >> b; while (b > 0) { num.PB(b % 10ll); b /= 10ll; } reverse(num.begin(), num.end()); ll x = solve(0, 0, 0, 0, 0); if (a == 0) { cout << x << '\n'; return 0; } memset(dp, -1ll, sizeof dp); num.clear(); a--; while (a > 0) { num.PB(a % 10ll); a /= 10ll; } reverse(num.begin(), num.end()); ll y = solve(0, 0, 0, 0, 0); cout << x - y << '\n'; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...