Submission #78921

#	Time	Username	Problem	Language	Result	Execution time	Memory
78921		doowey	Palindrome-Free Numbers (BOI13_numbers)	C++14	80 / 100	3 ms	748 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 = 1;i < 10; i ++ )
		dp[1][i][i] = 1;
	tot[1] = 9;
	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 xy){
	if(xy == -1)
		return 0;
	vector<int> idx;
	while(xy > 0){
		idx.push_back(xy % 10);
		xy /= 10;
	}
	ll dp2[20][10][10][2];
	memset(dp2, 0, sizeof dp2);
	int n = idx.size();
	int las;
	ll ans = 1;
	for(int i = 1; i <= n; i ++ ){
		las = idx.back();
		idx.pop_back();
		if(i != n)
			ans += tot[i];
		if(i == 1){
			for(int nx = 1; nx <= las; nx ++ ){
				dp2[i][nx][0][nx < las] = 1; 
			}
		}
		else if(i == 2){
			for(int pv = 1; pv <= 9; pv ++ ){
				for(int nx = 0; nx <= 9 ; nx ++ ){
					if(pv != nx){
						if(nx < las){
							dp2[i][pv][nx][1] += dp2[i - 1][pv][0][0] + dp2[i - 1][pv][0][1]; 
						}
						else if(nx == las){
							dp2[i][pv][nx][0] += dp2[i - 1][pv][0][0];
							dp2[i][pv][nx][1] += dp2[i - 1][pv][0][1];
						}
						else{
							dp2[i][pv][nx][1] += dp2[i - 1][pv][0][1];
						}
					}
				}
			}
		}
		else{
			for(int y = 0 ; y <= 9; y ++ ){
				for(int z = 0 ; z <= 9; z ++ ){
					for(int nx = 0; nx < 10; nx ++ ){
						if(nx == y or nx == z or y == z)
							continue;
						if(nx < las){
							dp2[i][z][nx][1] += dp2[i - 1][y][z][0] + dp2[i - 1][y][z][1];
						}
						else if(nx == las){
							dp2[i][z][nx][0] += dp2[i - 1][y][z][0];
							dp2[i][z][nx][1] += dp2[i - 1][y][z][1];
						}
						else{
							dp2[i][z][nx][1] += dp2[i - 1][y][z][1];
						}
					}
				}
			}
		}
	}
	for(int y = 0; y <= 9; y ++ ){
		for(int z = 0;z <= 9; z ++ ){
			for(int d = 0; d < 2; d ++ ){
				ans += dp2[n][y][z][d];
			}
		}
	}
	return ans;
}

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

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