Submission #1178959

#TimeUsernameProblemLanguageResultExecution timeMemory
1178959_dtq_Palindrome-Free Numbers (BOI13_numbers)C++20
72.50 / 100
1 ms840 KiB
#include<bits/stdc++.h> #define ll long long #define fi first #define se second #define pb push_back #define all(v) v.begin(), v.end() #define sz(x) (long long)(x.size()) using namespace std; ll a, b, maxn, t[30], dp[30][30][30][3]; ll calc( ll vt, ll x, ll y, bool c ) { if(vt == 0) return dp[vt][x][y][c] = 1; if(dp[vt][x][y][c] != -1) return dp[vt][x][y][c]; ll ans = 0; for( int w = (vt == maxn ? 1 : 0); w <= (c ? t[vt] : 9); w ++ ) { if(w == y || w == x) continue; ans += calc(vt - 1, y, w, c & (w == t[vt])); } return dp[vt][x][y][c] = ans; } ll solve( ll k ) { memset(dp, -1, sizeof(dp)); string s; while(k) { s = s + char(k % 10 + 48); k /= 10; } for( int w = 0; w < sz(s); w ++ ) { t[w + 1] = s[w] - 48; maxn = w + 1; } return calc( maxn, 20, 20, 1 ); } int main() { cin.tie(0)->sync_with_stdio(0); cin >> a >> b; if( a == 0 ) { cout << solve(b); return 0; } cout << solve(b) - solve(a - 1); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...