**Name:**UVa 11472 - Beautiful Numbers

**Link:**http://uva.onlinejudge.org/external/114/11472.html

**Time Limit:**3s

**Memory Limit:**

My suggested solution:

**Difficulty:**Medium

**Hint:**This problem can be solved with dp and bitmask technique. A 3D array of size 100 * 2 ^ 10 * 10 (about 1M), which is acceptable in memory limit, is needed to store the results. Then, the array can be filled by a recursive formula called f(i, j, k) - number of ways to make a number with i digits, using j as a mask and k is the last digit. The mask is definited as usual, i.e. if i-th digit from right to left of the mask value in binary notation is 1, digit i was used before and was not otherwise. Now f(i, j | (1 << k), k) = sum of all f(i - 1, j, k - 1) if(k - 1 >= 0), plus sum of all f(i - 1, j, k + 1) if (k + 1 < n). Remember to handle the special case when i = 1, i.e. no leading zero is allowed in beautiful numbers. The final answer is sum of all f(i, (1 << n) - 1, j), i = 1..m, j = 0..n-1

**Complexity:**M * N * 2 ^ N

**Algorithm:**dp + bitmask

**Related problem:**

My accepted code: