제출 #1355364

#제출 시각아이디문제언어결과실행 시간메모리
1355364blackscreen1Palindrome-Free Numbers (BOI13_numbers)C++20
100 / 100
1 ms352 KiB
#include <bits//stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef tree<long long, null_type, less<long long>, rb_tree_tag,
             tree_order_statistics_node_update>
    ordered_set;
typedef tree<long long, null_type, less_equal<long long>, rb_tree_tag,
             tree_order_statistics_node_update>
    ordered_multiset;
#define ll long long
#define iloop(m, h) for (auto i = m; i != h; i += (m < h ? 1 : -1))
#define jloop(m, h) for (auto j = m; j != h; j += (m < h ? 1 : -1))
#define kloop(m, h) for (auto k = m; k != h; k += (m < h ? 1 : -1))
#define lloop(m, h) for (auto l = m; l != h; l += (m < h ? 1 : -1))
#define pll pair<ll, ll>
#define INF 1000000000000000
#define MOD1 1000000007
#define MOD2 998244353
#define MOD3 1000000009
ll num[20], memo[20][11][11][2][2];
ll dp(ll cdi, ll prv, ll pprv, bool isb, bool isl) {
	if (cdi == -1) return 1;
	if (memo[cdi][prv][pprv][isb][isl] != -1) return memo[cdi][prv][pprv][isb][isl];
	ll cans = 0;
	if (!isb) {
		iloop(0, 10) {
			if (isl && i == 0) cans += dp(cdi-1, 10, prv, 0, 1);
			else if (i != prv && i != pprv) cans += dp(cdi-1, i, prv, 0, 0);
		}
	}
	else {
		iloop(0, num[cdi]+1) {
			if (isl && i == 0) {
				if (num[cdi] == 0) cans += dp(cdi-1, 10, prv, 1, 1);
				else cans += dp(cdi-1, 10, prv, 0, 1);
				continue;
			}
			if (i == prv || i == pprv) continue;
			cans += dp(cdi-1, i, prv, i == num[cdi], 0);
		}
	}
	return memo[cdi][prv][pprv][isb][isl] = cans;
}
ll prep(ll x) {
	memset(num, 0, sizeof(num));
	memset(memo, -1, sizeof(memo));
	ll ci = 0;
	while (x) {
		num[ci] = x%10;
		x /= 10, ci++;
	}
	return dp(19, 10, 10, 1, 1);
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	ll a, b;
	cin >> a >> b;
	cout << prep(b) - prep(a-1);
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...