ez problem 3

luogu_gza · 2026-08-04 20:46:49 · 学习·文化课

给定 n,m,a,b,c，定义函数列 f_k(x) 如下：f_0(x)=1,f_k(x)=\sum_{i=0}^{x}(ai^2+bi+c)f_{k-1}(i)。

对于 i \in [0,n]，求解 f_i(m)。

数据范围：1 \leq n \leq 10^5,1 \leq a,b,c,m <998244353。

来源：2026 杭电多校 R5 1001。

::::info[题解]

记 d_i=ai^2+bi+c。

考察用 ogf 刻画问题，答案不难表述为：

援用付公主的背包的手法，我们对里面的东西取对数，有结论：\ln(1-ax)=\sum_{i=0}^{+\infty}\frac{a^ix^i}{i}，因此 [x^k]\ln(\prod_{i=1}^{m}\frac 1{1-d_ix})=-\frac 1k \sum_{i=0}^{m}d_i^k。

接下来问题转化为怎么求对于 0 \leq k \leq n 求 \sum_{i=0}^{m}(ai^2+bi+c)^k，我们援用配方，将 ai^2+bi+c 转化为 A(i-r)^2+C 的形式，偏移一下 i，我们需要解决的问题变为了 \sum_{i=l}^{r}(Ai^2+C)^k。

也就是需要解决 \sum_{i=0}^{r}(Ai^2+C)^k=A^k\sum_{i=l}^{r}(i^2+\frac CA)^k=A^k\sum_{i=1}^{r}\sum_{j=0}^{k}\frac{k!}{j!(k-j)!}i^{2j}(\frac CA)^{k-j}=A^kk!\sum_{j=0}^{k}\frac{\sum_{i=1}^{r}i^{2j}}{j!}\times \frac{(\frac CA)^{k-j}}{(k-j)!}，令 F_j=\frac{\sum_{i=1}^{r}i^{2j}}{j!},G_i=\frac{(\frac CA)^{j}}{j!}，可以发现 \sum_{i=0}^{r}(Ai^2+C)^k=A^kk![x^k]FG。