\(N\) の桁数を \(n\) とします。
以下のような動的計画法を使います。
\(\mathrm{dp}[i][j]\) : 上位 \(i\) 桁であって以下の条件を全て満たすものの数

• \(N\) の上位 \(i\) 桁より真に小さい
• 全てが \(0\) ではない
• 先頭の \(0\) を取り除くとちょうど \(j\) 種類の数字を含む

\(\mathrm{dp}[i][j]\) からは以下の遷移があります。

• 上から \(i + 1\) 桁目に今までに使った \(j\) 種類のうちいずれかを使う場合 : \(\mathrm{dp}[i + 1][j]\) に \(\mathrm{dp}[i][j] \times j\) を足す
• 上から \(i + 1\) 桁目に今までに使った \(j\) 種類以外を使う場合 : \(\mathrm{dp}[i + 1][j + 1]\) に \(\mathrm{dp}[i][j] \times (16 - j)\) を足す

元々 \(\mathrm{dp}[i][j]\) の定義より \(N\) より真に小さいことが確定しているのでどの数字を使っても、次にできる上位 \(i + 1\) 桁は \(N\) の上位 \(i + 1\) 桁より小さくなります。
また、これとは別に \(\mathrm{dp}[i]\) に含まれないが \(\mathrm{dp}[i + 1]\) に影響するものの処理が必要です。

• 上位 \(i\) 桁が \(N\) のそれと一致していた場合
  上から \(i + 1\) 桁目は \(N\) の上から \(i + 1\) 桁目未満である必要がある
  上位 \(i\) 桁が \(N\) のそれに一致しているので今までに使った数字の集合は簡単に求められ、これを使って遷移後の \(i + 1\) 桁に含まれる数字の種類数も求めることができる
  
• 上位 \(i\) 桁がすべて \(0\) だった場合
  上から \(i + 1\) 桁目で初めて非 \(0\) な桁が出現する場合である
  \(N\) の最上位桁は非 \(0\) なので、\(i + 1\) 桁目に \(15\) 種類のどれを使っても、できる \(i + 1\) 桁は \(N\) の上位 \(i + 1\) 桁より小さくなる
  よって \(\mathrm{dp}[i + 1][1]\) に \(15\) を足せばよい

\(\mathrm{dp}[n][K]\) は \(N\) 未満の整数で問題文の条件を満たすものなので、\(N\) に等しいものも処理すれば答えは簡単に求められます。

適切に実装すれば計算量は、基数 (この問題では \(16\)) を \(d\) として \(O(nd) = O(\log(N)d)\) です。

この解法は kyopro_friends さんの指摘によるものです。ありがとうございます。