제출 #97253

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
97253		Shafin666	Palindrome-Free Numbers (BOI13_numbers)	C++14	100 / 100	5 ms	432 KiB

numbers

#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define pii pair<ll, ll>
#define to second
#define cost first
typedef long long ll;
typedef long double ld;
using namespace std;

std::vector<int> num;
ll dp[20][12][12][2][2];
string str;

ll answer(int idx, int a, int b, bool noconst, bool start) {
	if(idx == (int)str.size()) return 1;
	if(dp[idx][a][b][noconst][start] != -1) return dp[idx][a][b][noconst][start];

	ll ret = 0, limit;
	if(noconst) limit = 9; else limit = str[idx]-48; //num[idx];

	for(int i = 0; i <= limit; i++) {
		if(i == a || i == b) continue;
		if(i == 0 && start == 0) ret += answer(idx+1, 10, 10, 1, 0);
		else ret += answer(idx+1, b, i, noconst || (i < limit), 1);
	} return dp[idx][a][b][noconst][start] = ret;
}

ll solve(ll n) {
	//if(n < 0) return 0;
	//if(n < 10) return n+1;
	str = to_string(n);
//	num.clear();
//	while(n) {
//		num.pb(n%10);
//		n /= 10;
	//} 
//	reverse(num.begin(), num.end());
	memset(dp, -1, sizeof dp);
	return answer(0, 10, 10, 0, 0);
}

int main()
{
	//freopen("in.txt", "r", stdin);
	//freopen("out.txt", "w", stdout);

	ll a, b;

	cin >> a >> b;
	ll ans = solve(b);
	if(a > 0) ans -= solve(a-1);

	cout << ans << endl;
    return 0;
}

• Subtask 1: 25 / 25
• Subtask 2: 75 / 75