Submission #1244960

#	Time	Username	Problem	Language	Result	Execution time	Memory
1244960		kaiboy	Palindrome-Free Numbers (BOI13_numbers)	C++20	100 / 100	1 ms	328 KiB

numbers

#include <algorithm>
#include <iostream>

using namespace std;

const int N = 19;

int dd[N];
long long dp[10][10], dq[10][10];

long long solve(long long a) {
	if (a < 10)
		return a;
	int n = 0;
	for ( ; a; a /= 10)
		dd[n++] = a % 10;
	long long ans = 10;
	for (int i = 1; i + 1 < n; i++) {
		for (int d = 0; d < 10; d++)
			for (int e = 0; e < 10; e++) {
				long long x = 0;
				if (d != e)
					if (i == 1)
						x++;
					else
						for (int f = 0; f < 10; f++)
							if (d != f)
								x += dp[e][f];
				dq[d][e] = x;
				if (d)
					ans += x;
			}
		for (int d = 0; d < 10; d++)
			for (int e = 0; e < 10; e++)
				dp[d][e] = dq[d][e];
	}
	for (int i = n - 1; i >= 0; i--) {
		int d0 = dd[i];
		int d1 = i + 1 < n ? dd[i + 1] : -1;
		int d2 = i + 2 < n ? dd[i + 2] : -1;
		for (int d_ = i + 1 == n; d_ < d0; d_++) {
			if (d_ == d1 || d_ == d2)
				continue;
			if (!i) {
				ans++;
				continue;
			}
			for (int d = 0; d < 10; d++)
				for (int e = 0; e < 10; e++)
					dp[d][e] = e == d_ && d != e && d != d1;
			for (int j = i - 2; j >= 0; j--) {
				for (int d = 0; d < 10; d++)
					for (int e = 0; e < 10; e++) {
						long long x = 0;
						if (d != e)
							if (i == 1)
								x++;
							else
								for (int f = 0; f < 10; f++)
									if (d != f)
										x += dp[e][f];
						dq[d][e] = x;
					}
				for (int d = 0; d < 10; d++)
					for (int e = 0; e < 10; e++)
						dp[d][e] = dq[d][e];
			}
			for (int d = 0; d < 10; d++)
				for (int e = 0; e < 10; e++)
					ans += dp[d][e];
		}
		if (d0 == d1 || d0 == d2)
			break;
	}
	return ans;
}

int main() {
	long long l, r; cin >> l >> r;
	cout << solve(r + 1) - solve(l) << '\n';
	return 0;
}

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