Beautifulness

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';
}