Well, after all, I solved this problem, but it took a long time for me to find all mistakes in my calculations.

My idea was to generate F[N,K] in a O(log(N)*log(N)) time, which means an amount of numbers with N or less digits (in a certain base) with K one-digits. Then I wrote a function C(N, K), which finds an amount of numbers with K one-digits in [1, N] using F and deleting its first digit every time. Actually it's all about dynamic programming.

But I think there must be more clear and efficient solutions, than mine (O(log(N)*log(N)) for time and memory). If it does, please, would you be so kind to share it?