제출 #1216201

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1216201		a_xor_a	Palindrome-Free Numbers (BOI13_numbers)	C++20	62.50 / 100	1 ms	840 KiB

numbers

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define pb push_back
#define all(x) (x).begin(), (x).end()
const int N = 20, M = 12, K = 2;

void go() {
	ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
// #ifndef ONLINE_JUDGE
// 	freopen("in.txt", "r", stdin);
// 	freopen("out.txt", "w", stdout);
// #endif // ONLINE_JUDGE
}

ll dp[N][M][M][M][K];
int a[M];

ll Count(int pos, int x, int y, int z, ll sum, bool f){
	if(pos == 0) return 1;
	
	if(dp[pos][x][y][z][f] != -1) return dp[pos][x][y][z][f];
	
	ll res = 0;
	int lim = (f ? a[pos]: 9);
	for(int d = 0; d <= lim; d++){
		if((d == z && sum>0) || (d == y && sum >= 10)){
			continue;
		}
		res += Count(pos-1, y, z, d, sum * 10 + d, (f&&(d == a[pos]))); 
	}
	return dp[pos][x][y][z][f] = res; 
}

void solve(){
	ll p, q;
	cin >> p >> q;
	
	auto getAns =[&](ll x){
		int n = 0;
		while(x){
			a[++n] = x % 10, x/=10;
		}
		memset(dp, -1, sizeof dp);
		return Count(n, 10, 10, 10, 0, 1);
	};
	cout << getAns(q) - getAns(p-1);
}

int main(){
	go();
	int t=1;
	while(t--){
		solve();
	}
	return 0;
}

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