제출 #1275144

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1275144		kerem	Palindrome-Free Numbers (BOI13_numbers)	C++20	100 / 100	2 ms	584 KiB

numbers

#include <bits/stdc++.h>
using namespace std;
#define int int64_t
#define pb push_back
#define fr first
#define sc second
#define all(x) x.begin(),x.end()
#define sp << " " <<
#define N 200000
#define inf 1e15
typedef pair<int,int> pii;

const int mod=1e9+7;
int n,dp[18][2][10][10],pw[18]={1};

int get(int x,int i){return (x/pw[i])%10;}
int sz(int x){
	int ans=0;
	while(x)
		x/=10,ans++;
	return ans;
}
int calc(int X){
	if(X<0) return 0;
	if(X<10) return X+1;
	memset(dp,0,sizeof(dp));
	int m=sz(X),ans=10;
	
	for(int _=0;_<=9;_++){
		for(int __=0;__<=9;__++){
			if(_==__) continue;
			dp[1][1][_][__]=1;
			dp[1][0][_][__]=(_*10+__<=X%100);
			if(_) ans+=dp[1][2<m?1:0][_][__];
		}
	}
	for(int i=2;i<m;i++){
		int ind=get(X,i);
		for(int _=0;_<=9;_++){
			for(int __=0;__<=9;__++){
				if(_==__) continue;
				for(int ___=0;___<=9;___++){
					if(_==___ || __==___) continue;
					dp[i][1][_][__]+=dp[i-1][1][__][___];
					if(_==ind)
						dp[i][0][_][__]+=dp[i-1][0][__][___];
					if(_<ind)
						dp[i][0][_][__]+=dp[i-1][1][__][___];
				}
				if(_) ans+=dp[i][i+1<m?1:0][_][__];
			}
		}
	}
	return ans;
}
void solve(){
	for(int i=1;i<18;i++)
		pw[i]=pw[i-1]*10;
	int l,r;
	cin >> l >> r;
	cout << calc(r)-calc(l-1);
}
int32_t main(){
	//~ freopen("a.txt","r",stdin);
	//~ freopen("a.out","w",stdout);
	
	cout << fixed << setprecision(0);
	ios_base::sync_with_stdio(false);	
	cin.tie(NULL);cout.tie(NULL);
	
	int test=1;
	//~ cin >> test;
	while(test--) solve();
}

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