这题可以出到 $d_i\le 32000$，但仁慈的出题人并没有那么做。

正解是常系数齐次线性递推。这玩意有 $5$ 种解法：

• 暴力递推 $\Theta(k\max d_i)$
• 矩阵快速幂 $\Theta((\max d_i)^3\log k)$
• 特征方程 $\Theta(\log k),d\le 5$
• 多项式求逆 $\Theta(k\log k)$
• 多项式取模 $\Theta((\max d_i)\log(\max d_i)\log k)$

显然具体方法可以为矩阵快速幂或多项式取模。

简述下题意：

有一个可重集，有顺序地选若干次，每次从中选一个数，使最终的和 $\le k$，求方案数。

显然可以转化为生成函数：

设 $[x^m]g(x)$ 为和恰好为 $m$ 的方案数，$f(x)=\displaystyle\sum_ix^{d_i}$，

则 $g(x)=\displaystyle\sum_{i=0}^\infty f^i(x)=\dfrac{1}{1-f(x)}$

因为要求 $\le k$，做一遍前缀和——答案就是

$$\dfrac{[x^k]}{(1-x)(1-f(x))}$$

本题的 $k$ 很大，根据常系数齐次线性递推的一般理论，

设 $f^R(x)$ 为 $(1-x)(1-f(x))$ 翻转的结果，则我们只需要求出

$$x^k\bmod f^R(x)$$

多项式取模即可解决这个问题。

或者矩阵快速幂：矩阵下面放递推系数，上面斜着放 $1$。