P6073 『MdOI R1』Epic Convolution

小 Q 是神仙，尤其喜欢多项式。 这天小 K 问了道题： 给定长度 $n$ 的序列 $g,h$，求 $f$ 满足 $f_n=\sum\limits_{k=0}^{n}g_kh_{n-k}$。 小 Q 对小 K 说：你这个菜鸡，这不随便卷一下就行了吗，你 FFT 怎么学的了。 然后小 K 花了一个月学习 FFT 和 NTT。又跑过去问小 Q 一道题： 给定长度 $n$ 的序列 $g,h$，求 $f$ 满足 $f_n=\sum\limits_{k=0}^{n}\binom{n}{k}g_kh_{n-k}$。 小 Q 对小 K 说：你这个菜鸡，这不随便卷一下就行了吗，你 FFT 怎么学的了。 然后小 K 又花了一个月学习 FFT 和 NTT。又跑过去问小 Q 一道题： 给定长度 $n$ 的序列 $g,h$，求 $f$ 满足 $f_n=\sum\limits_{k=0}^{n}k^ng_kh_{n-k}$。 小 Q 对小 K 说：你这个菜鸡，这不随便卷一下就行了吗，你 FFT 怎么学的了。 然后他仔细看了一遍，傻眼了，发现他不会这道题。 为了吊打小 K，你需要告诉他 $4$ 个特殊情况的做法。

给定特定的序列 $g,h$，求 $f_n$ 满足 $f_n=\sum\limits_{k=0}^{n}k^ng_kh_{n-k}$。 本题有五个子任务，前四个子任务给定不同形式的 $g,h$，需要求出 $f_n$，第五个子任务不依赖于这个等式，但是形式上与此相似。 **注意，本题所有输出请对 $998244353$（$119\times 2^{23}+1$，一个质数）取模。** --- **Subtask 1（4 pts）：** 给定一个 $n$，你需要回答 $q$ 组询问，每组询问给定一个整数 $m$。 每组询问的 $g$ 和 $h$ 如下所示（$0\leq k\leq n$）： $$g_k=\begin{cases}1,&k

无

无

### 样例解释 1 在这组样例中，需要解决第一个子任务，$n=5,\ \ q=2$。 第一组询问中，$m=2$，则（省略了 $0$ 的加数项）： $$[g_0\ \ g_1\ \ g_2\ \ g_3\ \ g_4\ \ g_5]=[1\ \ 1\ \ 0\ \ 0\ \ 0\ \ 0] $$ $$[h_0\ \ h_1\ \ h_2\ \ h_3\ \ h_4\ \ h_5]=[1\ \ 1\ \ 1\ \ 1\ \ 1\ \ 1] $$ $$f_5=1^5\times g_1h_4=1$$ 第二组询问中，$m=3$，则： $$[g_0\ \ g_1\ \ g_2\ \ g_3\ \ g_4\ \ g_5]=[1\ \ 1\ \ 1\ \ 0\ \ 0\ \ 0]$$ $$[h_0\ \ h_1\ \ h_2\ \ h_3\ \ h_4\ \ h_5]=[1\ \ 1\ \ 1\ \ 1\ \ 1\ \ 1]$$ $$f_5=1^5\times g_1h_4+2^5\times g_2h_3=33$$ ------ ### 样例解释 2 在这组样例中，需要解决第二个子任务，$q=2$。 第一组询问中，$n=4,\ \ m=2$，则： $$[g_0\ \ g_1\ \ g_2\ \ g_3\ \ g_4]=[\dfrac{1}{6}\ \ \dfrac{1}{24}\ \ \dfrac{1}{120}\ \ \dfrac{1}{720}\ \ \dfrac{1}{5040}] $$ $$[h_0\ \ h_1\ \ h_2\ \ h_3\ \ h_4]=[0\ \ 0\ \ 1\ \ -1\ \ \dfrac{1}{2}] $$ $$f_5=1^4\times g_1h_3+2^4\times g_2h_2=\dfrac{11}{120} $$ $f_5=\dfrac{11}{120}$ 对 $998244353$ 取模后等于 $440891256$。 第二组询问范围过大，不进行样例解释。 ------ ### 样例解释 3 在这组样例中，需要解决第四个子任务，$q=2$。 第一组询问中，$n=4,\ \ m=2$，则： $$[g_0\ \ g_1\ \ g_2\ \ g_3\ \ g_4]=[0\ \ \ 1\ \ \ 2\ \ \ \dfrac{3}{2}\ \ \dfrac{2}{3}] $$ $$[h_0\ \ h_1\ \ h_2\ \ h_3\ \ h_4]=[1\ \ -1\ \ \dfrac{1}{2}\ \ -\dfrac{1}{6}\ \ \dfrac{1}{24}] $$ $$f_5=1^4\times g_1h_3+2^4\times g_2h_2+3^4\times g_3h_1+4^4\times g_4h_0=65 $$ 第二组询问范围过大，不进行样例解释。 --- ### 样例解释 4 在这组样例中，需要解决第五个子任务，$q=2$。 第一组询问中，$n=4,\ \ m=2$，则枚举 $k,i$： $$k=0,\ \ i=0:\ \ (k+1)^m\dfrac{(k+1)^{n+1}}{(k+1)!}\dfrac{\binom{2n+1}{i}(-1)^{m-k}}{(m-k-i)!(k+1)^i}=\dfrac{1}{2} $$ $$k=0,\ \ i=1:\ \ (k+1)^m\dfrac{(k+1)^{n+1}}{(k+1)!}\dfrac{\binom{2n+1}{i}(-1)^{m-k}}{(m-k-i)!(k+1)^i}=9 $$ $$k=0,\ \ i=2:\ \ (k+1)^m\dfrac{(k+1)^{n+1}}{(k+1)!}\dfrac{\binom{2n+1}{i}(-1)^{m-k}}{(m-k-i)!(k+1)^i}=36 $$ $$k=1,\ \ i=0:\ \ (k+1)^m\dfrac{(k+1)^{n+1}}{(k+1)!}\dfrac{\binom{2n+1}{i}(-1)^{m-k}}{(m-k-i)!(k+1)^i}=-64 $$ $$k=1\ \ i=1:\ \ (k+1)^m\dfrac{(k+1)^{n+1}}{(k+1)!}\dfrac{\binom{2n+1}{i}(-1)^{m-k}}{(m-k-i)!(k+1)^i}=-288 $$ $$k=2\ \ i=0:\ \ (k+1)^m\dfrac{(k+1)^{n+1}}{(k+1)!}\dfrac{\binom{2n+1}{i}(-1)^{m-k}}{(m-k-i)!(k+1)^i}=\dfrac{729}{2} $$ 全部相加，结果为 $58$。 第二组询问范围过大，不进行样例解释。 --- ### 数据范围 **本题采用捆绑测试，不同 Subtask 的题意不同。** | 子任务编号 | $q\leq$ | $n\leq$ | $m\leq$ | 分值 | | :--------: | :------------: | :------------: | :------------: | :--: | | 1 | $5\times 10^5$ | $10^5$ | $\min(10^5,n)$ | 4 | | 2 | $5\times 10^5$ | $2\times 10^5$ | $20$ | 16 | | 3 | $20$ | $998244352$ | $20$ | 16 | | 4(31-40) | $5\times 10^5$ | $2\times 10^5$ | $10$ | 32 | | 4(51-60) | $20$ | $10^{10^5}$ | $10$ | 32 | | 5 | $5\times 10^5$ | $2\times 10^3$ | $2\times 10^3$ | 32 | 所有输入均为正整数。