#include <bits/stdc++.h>
#define va first
#define vb second
#define lb lower_bound
#define ub upper_bound
#define bs binary_search
#define pp push_back
#define ep emplace_back
#define all(v) (v).begin(),(v).end()
#define szz(v) ((int)(v).size())
#define bi_pc __builtin_popcount
#define bi_pcll __builtin_popcountll
#define bi_tz __builtin_ctz
#define bi_tzll __builtin_ctzll
#define fio ios_base::sync_with_stdio(0);cin.tie(0);
#ifdef TAMREF
#define debug(...) fprintf(stderr, __VA_ARGS__)
#else
#define debug(...) 42
#endif
using namespace std;
template<typename ...Args>
void logger(string vars, Args&&... values) {
cerr << vars << " = ";
string delim = "";
(..., (cerr << delim << values, delim = ", "));
cerr << '\n';
}
#ifdef TAMREF
#define deb(...) logger(#__VA_ARGS__, __VA_ARGS__)
#else
#define deb(...) 42
#endif
using ll = unsigned long long; using lf = long double;
using pii = pair<int,int>; using ppi = pair<int,pii>;
using pll = pair<ll,ll>; using pff = pair<lf,lf>;
using ti = tuple<int,int,int>;
using base = complex<double>;
const lf PI = 3.14159265358979323846264338L;
template <typename T>
inline T umax(T& u, T v){return u = max(u, v);}
template <typename T>
inline T umin(T& u, T v){return u = min(u, v);}
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll dp[19][10][10]; // (digits left, prev^2 digit, prev digit)
ll dp_1d[19][10];
ll dp_0d[19];
ll ten[19] = {1};
ll solve(ll b) {
ll ans = 0;
for(int n = 18; n >= 0; n--) {
debug("n = %d, ans = %llu\n", n, ans);
ll qb = b / ten[n];
if(qb == 0) continue;
if(qb < 10) {
debug("adding dp_0d[%d] = %llu\n", n, dp_0d[n]);
ans += dp_0d[n];
for(int i = 1; i < qb; i++) ans += dp_1d[n][i];
continue;
}
qb %= 1000;
for(int i = 0; i < qb % 10; i++) if(qb < 100 || i != qb / 100) ans += dp[n][(qb / 10) % 10][i];
if(qb % 10 == (qb / 10) % 10 || (qb >= 100 && qb % 10 == qb / 100)) break;
}
debug("final ans = %llu\n", ans);
return ans;
}
int main(){
for(int i = 1; i < 19; i++) ten[i] = ten[i-1] * 10;
for(int i = 0; i < 10; i++) {
for(int j = 0; j < 10; j++) {
if(i == j) continue;
dp[0][i][j] = 1;
}
}
for(int n = 1; n < 19; n++) {
for(int i = 0; i < 10; i++) {
for(int j = 0; j < 10; j++) {
if(i == j) continue;
for(int k = 0; k < 10; k++) {
if(i == k ||j == k) continue;
dp[n][i][j] += dp[n-1][j][k];
}
}
}
}
for(int i = 0; i < 10; i++) dp_1d[0][i] = 1;
for(int n = 1; n < 19; n++) {
for(int i = 1; i < 10; i++) {
for(int j = 0; j < 10; j++) {
if(i == j) continue;
dp_1d[n][i] += dp[n-1][i][j];
}
}
}
dp_0d[0] = 1; // 0 is non-palindrome number
for(int n = 1; n < 19; n++) {
dp_0d[n] += dp_0d[n-1];
for(int i = 1; i < 10; i++) {
dp_0d[n] += dp_1d[n-1][i];
}
}
ll a, b;
cin >> a >> b;
cout << solve(b+1) - solve(a) << '\n';
}
Compilation message
numbers.cpp: In function 'll solve(ll)':
numbers.cpp:19:20: warning: statement has no effect [-Wunused-value]
19 | #define debug(...) 42
| ^~
numbers.cpp:54:9: note: in expansion of macro 'debug'
54 | debug("n = %d, ans = %llu\n", n, ans);
| ^~~~~
numbers.cpp:19:20: warning: statement has no effect [-Wunused-value]
19 | #define debug(...) 42
| ^~
numbers.cpp:58:13: note: in expansion of macro 'debug'
58 | debug("adding dp_0d[%d] = %llu\n", n, dp_0d[n]);
| ^~~~~
numbers.cpp:60:30: warning: comparison of integer expressions of different signedness: 'int' and 'll' {aka 'long long unsigned int'} [-Wsign-compare]
60 | for(int i = 1; i < qb; i++) ans += dp_1d[n][i];
| ~~^~~~
numbers.cpp:64:26: warning: comparison of integer expressions of different signedness: 'int' and 'll' {aka 'long long unsigned int'} [-Wsign-compare]
64 | for(int i = 0; i < qb % 10; i++) if(qb < 100 || i != qb / 100) ans += dp[n][(qb / 10) % 10][i];
| ~~^~~~~~~~~
numbers.cpp:64:59: warning: comparison of integer expressions of different signedness: 'int' and 'll' {aka 'long long unsigned int'} [-Wsign-compare]
64 | for(int i = 0; i < qb % 10; i++) if(qb < 100 || i != qb / 100) ans += dp[n][(qb / 10) % 10][i];
| ~~^~~~~~~~~~~
numbers.cpp:19:20: warning: statement has no effect [-Wunused-value]
19 | #define debug(...) 42
| ^~
numbers.cpp:67:5: note: in expansion of macro 'debug'
67 | debug("final ans = %llu\n", ans);
| ^~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Correct |
1 ms |
212 KB |
Output is correct |
| 5 |
Correct |
0 ms |
212 KB |
Output is correct |
| 6 |
Correct |
0 ms |
212 KB |
Output is correct |
| 7 |
Correct |
0 ms |
212 KB |
Output is correct |
| 8 |
Correct |
1 ms |
212 KB |
Output is correct |
| 9 |
Correct |
0 ms |
212 KB |
Output is correct |
| 10 |
Correct |
0 ms |
212 KB |
Output is correct |
| 11 |
Correct |
0 ms |
212 KB |
Output is correct |
| 12 |
Correct |
1 ms |
212 KB |
Output is correct |
| 13 |
Correct |
0 ms |
212 KB |
Output is correct |
| 14 |
Correct |
0 ms |
212 KB |
Output is correct |
| 15 |
Correct |
0 ms |
212 KB |
Output is correct |
| 16 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 17 |
Correct |
0 ms |
212 KB |
Output is correct |
| 18 |
Correct |
0 ms |
212 KB |
Output is correct |
| 19 |
Correct |
0 ms |
212 KB |
Output is correct |
| 20 |
Correct |
0 ms |
212 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Correct |
0 ms |
212 KB |
Output is correct |
| 5 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 6 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 7 |
Correct |
0 ms |
212 KB |
Output is correct |
| 8 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 9 |
Correct |
0 ms |
212 KB |
Output is correct |
| 10 |
Correct |
0 ms |
212 KB |
Output is correct |
| 11 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 12 |
Correct |
0 ms |
212 KB |
Output is correct |
| 13 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 14 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 15 |
Correct |
0 ms |
212 KB |
Output is correct |
| 16 |
Correct |
0 ms |
212 KB |
Output is correct |
| 17 |
Correct |
0 ms |
212 KB |
Output is correct |
| 18 |
Correct |
0 ms |
212 KB |
Output is correct |
| 19 |
Correct |
0 ms |
212 KB |
Output is correct |
| 20 |
Correct |
0 ms |
212 KB |
Output is correct |
| 21 |
Correct |
0 ms |
212 KB |
Output is correct |
| 22 |
Correct |
0 ms |
212 KB |
Output is correct |
| 23 |
Correct |
0 ms |
212 KB |
Output is correct |
| 24 |
Correct |
0 ms |
212 KB |
Output is correct |
| 25 |
Correct |
1 ms |
212 KB |
Output is correct |
| 26 |
Correct |
0 ms |
212 KB |
Output is correct |
| 27 |
Correct |
0 ms |
212 KB |
Output is correct |
| 28 |
Correct |
1 ms |
212 KB |
Output is correct |
| 29 |
Correct |
0 ms |
212 KB |
Output is correct |
| 30 |
Correct |
0 ms |
212 KB |
Output is correct |
| 31 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 32 |
Correct |
0 ms |
212 KB |
Output is correct |
| 33 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 34 |
Correct |
0 ms |
212 KB |
Output is correct |
| 35 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 36 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 37 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 38 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 39 |
Correct |
0 ms |
212 KB |
Output is correct |
| 40 |
Correct |
0 ms |
212 KB |
Output is correct |
| 41 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 42 |
Correct |
0 ms |
212 KB |
Output is correct |
| 43 |
Correct |
0 ms |
212 KB |
Output is correct |
| 44 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 45 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
