题目大意

定义一个序列的权值为所有元素的乘积

求所有长度为 $k$ 的正整数序列中，满足所有元素的和小于等于 $S$，把它们的权值加起来输出

答案模素数 $p$，其中 $1 \le k,S \le 10^{18}, 2 \le p \le 5 \times 10^6$

题解

设 $f_{i,j}$ 表示长度为 $i$，和为 $j$ 的答案，则：

$$
f_{i,j}=\sum_{k \ge 1}f_{i-1,j-k} \cdot k
$$

生成函数为：

$$
\left(x \left( \frac{\mathbb{d}\frac{1}{1-x}}{\mathbb{d}x} \right)\right)^n = x^n( (-1) (1-x)^{-2} (-1) )^n=\frac{x^n}{(1-x)^{2n}}
$$

由于要求前缀和，再卷上 $\frac{1}{(1-x)}$，也就是：

$$
\frac{x^n}{(1-x)^{2n+1}}
$$

因为：

$$
[x^n]\frac{1}{(1-x)^k}={n+k-1 \choose k-1}
$$

所以：

$$
[x^S]\frac{x^k}{(1-x)^{2k+1}}= {S - k + 2k \choose 2k+1-1} = {S+k \choose 2k}
$$

卢卡斯定理一下就好了