제출 #534935

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

numbers

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

#define MOD 998244353
#define INF 1000000001
#define LNF 1000000000000000001
#define int ll

#define MAX 100000
#define MAXLOG 17

#define int ll

typedef pair<int,int> pii;

pii bruh(int x){
	pii ret = {1,1};
	while(x > 9){
		x/=10;
		ret.first++;
		ret.second *= 10;
	}
	return ret;
}

int powon[19];
int dp[19][2][11][11];

int pre(int x){
	if(x < 0)
		return 0;
	for(int i = 0;i < 19;i++)
		for(int j = 0;j < 2;j++)
			for(int k = 0;k < 11;k++)
				for(int l = 0;l < 11;l++)
					dp[i][j][k][l] = 0;

	pii cum = bruh(x);

	dp[cum.first][1][10][10] = 1;

	for(int i = cum.first;i >= 1;i--)
		for(int j = 0;j < 2;j++)
			for(int k = 0;k < 11;k++)
				for(int l = 0;l < 11;l++){
					if(dp[i][j][k][l] == 0)
						continue;
					
					int mx = 9;
					if(j == 1){
						mx = x/powon[i-1]%10;
					}

					int mn = 0;
					if(k == 10 && i > 1)
						mn = 1;

					for(int m = mx;m >= mn;m--){
						if(m != k && m != l){
							int flag = j && (m == x/powon[i-1]%10);
							dp[i-1][flag][m][k] += dp[i][j][k][l];
							// cout << i-1 << ' ' << flag << ' ' << m << ' ' << k << '+' << dp[i][j][k][l] << '\n';
						}
					}
					if(i > 1 && k == 10){
						dp[i-1][0][10][k] += dp[i][j][k][l];
						// cout << i-1 << ' ' << 0 << ' ' << 10 << ' ' << k << '+' << dp[i][j][k][l] << '\n';
					}
				}
	
	int ret = 0;
	for(int j = 0;j < 2;j++)
			for(int k = 0;k < 10;k++)
				for(int l = 0;l < 11;l++){
					// if(dp[0][j][k][l] > 0)
					// 	cout << 0 << ' ' << j << ' ' << k << ' ' << l << ' ' << dp[0][j][k][l] << '\n';
					ret += dp[0][j][k][l];
				}

	return ret;
}	

void solve(){
//#define TEST
	int curr = 1;
	for(int i = 0;i < 19;i++){
		powon[i] = curr;
		curr *= 10;
	}

	// for(int i = 1;i < 100000;i++){
	// 	if(pre(i) != brute(i)){
	// 		cout << i << ' ' << pre(i) << ' ' << brute(i) << '\n';
	// 	}
	// }
	int a,b;cin >> a >> b;
	// cout << a << ' ' << b << '\n';
	cout << pre(b)-pre(a-1);
}

signed main(){
	cin.tie(0);
	ios_base::sync_with_stdio(0);
#ifdef DEBUG
	freopen("i.txt","r",stdin);
	freopen("o.txt","w",stdout);
#endif
	int t = 1;
#ifdef TEST
	cin >> t;
#endif
	while(t--){
		solve();
	}

	return 0;
}

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