Submission #78900

#TimeUsernameProblemLanguageResultExecution timeMemory
78900dooweyPalindrome-Free Numbers (BOI13_numbers)C++14
22.50 / 100
3 ms928 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int,int> pii; typedef double db; #define fi first #define se second #define mp make_pair #define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); #define all(x) ((x).begin(),(x).end()) #define len(x) ((int)(x).size()) const int N = 19; ll dp[N][11][11]; ll tot[N]; void init(){ for(int i = 0;i < 10; i ++ ) dp[1][i][i] = 1; tot[1] = 10; tot[2] = 9 * 9; for(int i = 0; i < 10; i ++ ){ for(int j = 0;j < 10; j ++ ){ if(i != j and i > 0) dp[2][i][j] = 1; } } for(int num = 2; num < N - 1; num ++ ){ for(int x = 0; x < 10; x ++ ){ for(int z = 0;z < 10; z ++ ){ for(int nx = 0; nx < 10; nx ++ ){ if(nx != z and nx != x){ dp[num + 1][z][nx] += dp[num][x][z]; tot[num + 1] += dp[num + 1][z][nx]; } } } } } } ll calc(ll x){ if(x == -1) return 0; vector<int> idx; do{ idx.push_back(x % 10); x /= 10; }while(x > 0); if(idx.size() == 1) return idx[0] + 1; if(idx.size() == 2){ ll ans = 10; for(int y = 0; y < 10; y ++ ){ for(int z = 0; z < 10; z ++ ){ if(y > 0 and y != z and y * 10 + z <= idx[0] * 10 + idx[1]){ ans ++ ; } } } return ans; } reverse(idx.begin(), idx.end()); ll ans = tot[1]; ll dp2[20][10][10][2]; memset(dp2, 0, sizeof dp2); for(int y = 0 ; y < 10; y ++ ){ for(int z = 0; z < 10 ; z ++ ){ if(y != 0 and y != z and y * 10 + z <= idx[0] * 10 + idx[1]){ dp2[2][y][z][(y * 10 + z) != (idx[0] * 10 + idx[1])] ++; } } } int p = 3; for(auto xx : idx){ ans += tot[p - 1]; for(int y = 0; y < 10; y ++ ){ for(int z = 0; z < 10 ; z ++ ){ for(int nx = 0; nx < 10; nx ++ ){ if(y != nx and z != nx){ if(nx > xx){ dp2[p][z][nx][1] += dp2[p - 1][y][z][1]; } else if(nx < xx){ dp2[p][z][nx][1] += dp2[p - 1][y][z][0] + dp2[p - 1][y][z][1]; } else{ dp2[p][z][nx][0] += dp2[p - 1][y][z][0]; dp2[p][z][nx][1] += dp2[p - 1][y][z][1]; } } } } } p ++ ; } for(int y = 0; y < 10; y ++ ){ for(int z = 0; z < 10; z ++ ){ ans += dp2[idx.size()][y][z][0] + dp2[idx.size()][y][z][1]; } } return ans; } int main(){ fastIO; init(); ll a, b; cin >> a >> b; cout << calc(b) - calc(a - 1); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...