简化题意：对于每一个 $L$，求出有多少个长度为 $L+1$ 的非负整数序列 $a$，满足 $\sum_{i=0}^{L} a_i k^i \leq n$，并且 $a_{L}>0$。
我们注意题目要求的和是小于等于一个数，这不太方便。我们可以把它转化成和等于一个数的形式，其实就是和为 $nk$ 的方案数，这就相当于在最后的和后面乘上一个 $k$，再一直加一使得最终的值为 $nk$ 。容易发现这是一一对应的，最后的 $L$ 只需在原来基础上减一即可。于是我们现在只需要求 $\sum_{i=0}^{L} a_i k^i = n$ 的方案数。
在这个基础上，有两种不同的思考方式：
解法1
我们可以考虑把 $n$ 写成 $k$ 进制的形式，因为最后的 $a_i$ 可能 $\geq k$ ，于是就考虑从高位往低位不断退位，计算退位的方案数，需要满足 $L$ 的高位都为 $0$，第 $L$ 位不为 $0$。所以可以先把 $L$ 的高位先退到第 $L$ 位。再从第 $L$ 位开始从高到低依次退位。
我们记录 $f_{i,x}$ 表示第 $i$ 位当前的值为 $x$，往后退位直到第 $0$ 位的方案数。$g_{i,x}$ 表示第 $i+1$ 位相第 $i$ 位退了 $x$ 位 (注意是第 $i$ 位得到了 $x$ )，往后退位直到第 $0$ 位的方案数。
容易写出转移：
- $f_{i,x}= \sum_{j=0}^x g_{i-1,jk}$
- $g_{i,x}= f_{i,x+c_i} $ ( $c_i$ 表示 $n$ 写成 $k$ 进制下的第 $i$ 位)
初值 ：$f_{0,i}=1$， $g_{0,i}=1$
对于答案，你可以从低到高枚举每一位。当前是第 $i$ 位，$c_i=n \bmod k$ ，那么 $ans_{i-1} = f_{i,n-1}$ ，注意是 $n-1$ 因为第 $i$ 位不能全退了，最后 $n$ 再除以 $k$。这样就只需要 $\log_k^n$ 的扫一遍即可。
考虑如何求 $f$ 和 $g$ ，第二维可能很大，没法直接存，但我们发现 $f_{i,x}$ 和 $g_{i,x}$ 是一个关于 $x$ 的 $i$ 次多项式，运用归纳法可以轻松证明。类似于 $\sum_{i=0}^x i^k$ 是 $k+1$ 次多项式的证明。
于是我们便可以通过拉格朗日插值求出 $f_i$ 和 $g_i$ ，因为 $f$ 和 $g$ 只是 $x$ 的加减，所以只需要记录 $f$ 即可。而这道题需要高精，复杂度瓶颈在高精乘 ，总复杂度为 $O((log_kn)3)$ 再乘上高精乘的复杂度。
另外，本题只需要高精除低精，插值时前缀和后缀都是一个组合数的形式，可以参考 代码。
解法2
有一种不需要插值的做法，但复杂度较高。
就是根据 $\sum_{i=0}^{L} a_i k^i = n$，我们再把 $a_i$ 写成 $k$ 进制的形式。设 $n$ 写成 $k$ 进制的最高位为 $m$。
$\sum_{i=0}^L ki\sum_{j=0}m b_{i,j} k^j = n$
$b_{i,j}$ 表示把 $a_i$ 写成 $k$ 进制下的第 $j$ 位。
$\sum_{i=0}^L \sum_{j=0}^m b_{i,j} k^{i+j} = n$
我们先枚举 $i+j$ ，设为 $d$，推出：
$\sum_{d=0}^m k^d \sum_{i=0}^{\min(L,d)} b_{i,d-i}= n$
我们注意 $b_{i,j} < k $ ，记 $f_d$ 为 $\sum_{i=0}^{\min(L,d)} b_{i,d-i}$，那么 $f_d \leq (k-1) \times (\min(L,d)+1)$ 。
于是方案数就是，先枚举所有的序列 $f$ ,再枚举 $d$ ,把 $f_d$ 个球放到 $\min(L,d)+1$ 个盒子，每个盒子小于 $k$ 个的方案数。这可以直接组合数预处理。
那么因为 $f_i$ 的值域很小，就可以直接 DP 了。这就是一个经典的数位 DP 问题，$f_{i,j}$ 表示考虑了 $0 \sim i$ 位，第 $i$ 位的值为 $j$ 的方案数。$j$ 的范围只有 $k \times \log_k^n$ 级别，所以直接转移即可。复杂度 $O((\log_kn)4)$ 再乘上高精乘的复杂度，比第一种做法好写很多。
标签：方案,进制,min,题解,sum,2019,复杂度,Day,log From： https://www.cnblogs.com/xzc0920/p/17715967.html