Beautifulness
Time limit: 1 s.
Memory limit: 256 MB
A number is beautiful if all of its digits are distinct. For example, the numbers \(123\), \(5926\), and \(9\) are beautiful, while the numbers \(121\), \(99\), and \(1090\) are not beautiful.
You are given two positive integers \(m\) and \(n\). Count the number of beautiful integers between \(m\) and \(n\) - including \(m\) and \(n\).
Input
The only line contains two integers \(m\) and \(n\) (\(1 \leq m \leq n \leq 10^7\)).
Output
Print a single integer: the number of beautiful integers between \(m\) and \(n\).
Scoring
| Subtask | Additional constraints | Points |
|---|---|---|
| \(1\) | \(m = n \le 100\) | \(7\) |
| \(2\) | \(n \le 100\) | \(11\) |
| \(3\) | \(m = n \le 1000\) | \(13\) |
| \(4\) | \(n \le 1000\) | \(14\) |
| \(5\) | \(n - m \le 10^5\) | \(19\) |
| \(6\) | \(n \le 10^6\) | \(16\) |
| \(7\) | no additional constraints | \(20\) |
Example
Input
90 130
Output
26
Note
Explanation: There are \(41\) numbers between \(90\) and \(130\) (inclusive). Among them, the following \(15\) do not have all distinct digits. \(99, 100, 101, 110, 111, 112, 113, 114, 115, 116, 117, 118, 119, 121, 122\) So the answer is \(41 - 15 = 26\).
Solution
Let \(F(x)\) be the number of positive beautiful integers not greater than \(x\). The required answer is \(F(n)-F(m-1)\).
Compute \(F(x)\) with digit DP. Process the digits from left to right and keep a bitmask of the digits already used. Leading zeroes do not count as digits. A digit whose bit is already set cannot be chosen again.
There are only \(O(8\cdot2^{10})\) states, each with at most 10 transitions.
#include <cstring>
#include <iostream>
#include <string>
using namespace std;
string digits;
long long memo[10][1 << 10][2];
long long countWays(int position, int mask, bool started, bool tight) {
if (position == (int)digits.size()) {
return started;
}
if (!tight && memo[position][mask][started] != -1) {
return memo[position][mask][started];
}
int limit = tight ? digits[position] - '0' : 9;
long long answer = 0;
for (int digit = 0; digit <= limit; digit++) {
bool nextTight = tight && (digit == limit);
if (!started && digit == 0) {
answer += countWays(position + 1, mask, false, nextTight);
} else if ((mask & (1 << digit)) == 0) {
answer += countWays(
position + 1,
mask | (1 << digit),
true,
nextTight
);
}
}
if (!tight) {
memo[position][mask][started] = answer;
}
return answer;
}
long long countBeautiful(long long x) {
if (x <= 0) return 0;
digits = to_string(x);
memset(memo, -1, sizeof(memo));
return countWays(0, 0, false, true);
}
int main() {
long long m, n;
cin >> m >> n;
cout << countBeautiful(n) - countBeautiful(m - 1) << '\n';
}