1343. Count Numbers with Unique Digits (Bitmask DP)

Count the integers x with 0 <= x < base^n whose representation in the given base has no repeated digit. Numbers are written without leading zeros, and 0 itself counts as the single digit 0. The classic decimal problem is the special case base = 10.

Input: A JSON object {"n": <length>, "base": <radix>} with 0 <= n <= 15 and 2 <= base <= 16.

Output: Return the count of such integers.

Examples

Input: {"n":2,"base":10}
Output: 91
Explanation: Classic decimal case: 91 numbers below 100 have distinct digits.

Input: {"n":3,"base":2}
Output: 3
Explanation: In binary only 0, 1 and 2 (10) qualify -> 3.

Constraints

• 0 <= n <= 15
• 2 <= base <= 16

Asked by