Submission #78900

#	Time	Username	Problem	Language	Result	Execution time	Memory
78900		doowey	Palindrome-Free Numbers (BOI13_numbers)	C++14	22.50 / 100	3 ms	928 KiB

numbers

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef double db;

#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define all(x) ((x).begin(),(x).end())
#define len(x) ((int)(x).size())

const int N = 19;
ll dp[N][11][11];

ll tot[N];

void init(){
	for(int i = 0;i < 10; i ++ )
		dp[1][i][i] = 1;
	tot[1] = 10;
	tot[2] = 9 * 9;
	for(int i = 0; i < 10; i ++ ){
		for(int j = 0;j < 10; j ++ ){
			if(i != j and i > 0)
				dp[2][i][j] = 1;
		}
	}
	for(int num = 2; num < N - 1; num ++ ){
		for(int x = 0; x < 10; x ++ ){
			for(int z = 0;z < 10; z ++ ){
				for(int nx = 0; nx < 10; nx ++ ){
					if(nx != z and nx != x){
						dp[num + 1][z][nx] += dp[num][x][z];
						tot[num + 1] += dp[num + 1][z][nx];
					}
				}
			}
		}
	}
}

ll calc(ll x){
	if(x == -1)
		return 0;
	vector<int> idx;
	do{
		idx.push_back(x % 10);
		x /= 10;
	}while(x > 0);
	if(idx.size() == 1)
		return idx[0] + 1;
	if(idx.size() == 2){
		ll ans = 10;
		for(int y = 0; y < 10; y ++ ){
			for(int z = 0; z < 10; z ++ ){
				if(y > 0 and y != z and y * 10 + z <= idx[0] * 10 + idx[1]){
					ans ++ ;
				} 
			}
		}
		return ans;
	}
	reverse(idx.begin(), idx.end());
	ll ans = tot[1];
	ll dp2[20][10][10][2];
	memset(dp2, 0, sizeof dp2);
	for(int y = 0 ; y < 10; y ++ ){
		for(int z = 0; z < 10 ; z ++ ){
			if(y != 0 and y != z and y * 10 + z <= idx[0] * 10 + idx[1]){
				dp2[2][y][z][(y * 10 + z) != (idx[0] * 10 + idx[1])] ++;
			}
		}
	}
	int p = 3;
	for(auto xx : idx){
		ans += tot[p - 1];
		for(int y = 0; y < 10; y ++ ){
			for(int z = 0; z < 10 ; z ++ ){
				for(int nx = 0; nx < 10; nx ++ ){
					if(y != nx and z != nx){
						if(nx > xx){
							dp2[p][z][nx][1] += dp2[p - 1][y][z][1];
						}
						else if(nx < xx){
							dp2[p][z][nx][1] += dp2[p - 1][y][z][0] + dp2[p - 1][y][z][1];
						}
						else{
							dp2[p][z][nx][0] += dp2[p - 1][y][z][0];
							dp2[p][z][nx][1] += dp2[p - 1][y][z][1];
						}
					}
				}
			}
		}
		p ++ ;
	}
	for(int y = 0; y < 10; y ++ ){
		for(int z = 0; z < 10; z ++ ){
			ans += dp2[idx.size()][y][z][0] + dp2[idx.size()][y][z][1];
		}
	}
	return ans;
}

int main(){
	fastIO;
	init();
	ll a, b;
	cin >> a >> b;
	cout << calc(b) - calc(a - 1);
	return 0;
}

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