1001. 简单多项式问题

题目描述

https://acm.hdu.edu.cn/downloads/2026杭电多校5-题目集new2.pdf

给定非负整数 $n,m,a,b,c$。定义一列函数 $f_k\ (x)$ 如下：

$$f_0(x)=1$$ $$f_k(x)=\sum_{i=0}^{x}(a i^2+b i+c)\,f_{k-1}(i)\qquad (k\ge 1)$$

请你对于每个整数 $k\in[0,n]$，求出 $f_k\ (m)$ 的值。

由于答案可能很大，你只需要输出它们对 $998244353$ 取模后的结果。

输入格式

第一行输入一个数代表数据组数 $T$ $（1\le T \le 10$）。

对于每组数据，输入一行包含五个整数 $n,m,a,b,c$（$1\le n\le 10^5,1\le a,b,c,m<998244353$）。

输出格式

对于每组输入，输出一行，共 $n+1$ 个整数。

第 $k+1$ 个整数表示 $f_k\ (m)\bmod 998244353$ 的值，其中 $0\le k\le n$。相邻两个整数之间用一个空格隔开。

样例输入

5
1 1 1 1 1
2 1 1 1 1
9 2 9 1 10
1 10 13 55 73
7 26 210 632 594

样例输出

1 4
1 4 13
1 78 4444 228312 11268976 547210848 438767526 651221129 502577246 963625864
1 8833
1 1540080 206229124 966328099 314496902 584769984 53114709 515981297

提示

已知 $a=b=c=1$，所以 $a i^2+b i+c=i^2+i+1$。

由定义，$f_0\ (x)=1$，因此 $f_0\ (1)=1$。

接下来计算 $f_1\ (1)=\sum_{i=0}^{1}(i^2+i+1)f_0(i)$。

由于 $f_0\ (i)=1$，所以 $f_1\ (1)=(0^2+0+1)+(1^2+1+1)=1+3=4$。

进一步，$f_2\ (1)=\sum_{i=0}^{1} (i^2+i+1)f_1\ (i)$。

先求出中间值：$f_1\ (0)=\sum_{i=0}^{0} (i^2+i+1)f_0\ (i)=1$，$f_1\ (1)=4$。

于是

$$\begin{aligned} f_2 (1)&=\ (0^2+0+1)\cdot f_1\ (0)+\ (1^2+1+1)\cdot f_1\ (1)\\ &=1\cdot 1+3\cdot 4\\ &=13 \end{aligned}$$

所以 $f_0\ (1)=1, f_1\ (1)=4, f_2\ (1)=13$。

来源：2026杭电多校-测试专用（电子科大） 原题链接：http://acm.hdu.edu.cn/contest/problem_show.php?cid=1233&pid=1001