P6073 "MdOI R1" Epic Convolution

Little Q is a genius and especially likes polynomials. One day, Little K asked a question: Given two sequences $g, h$ of length $n$, find $f$ such that $f_n=\sum\limits_{k=0}^{n}g_kh_{n-k}$. Little Q said to Little K: You are such a newbie. Isn’t this just an easy convolution? What did you learn FFT for? Then Little K spent a month learning FFT and NTT, and went to ask Little Q another question: Given two sequences $g, h$ of length $n$, find $f$ such that $f_n=\sum\limits_{k=0}^{n}\binom{n}{k}g_kh_{n-k}$. Little Q said to Little K: You are such a newbie. Isn’t this just an easy convolution? What did you learn FFT for? Then Little K spent another month learning FFT and NTT, and went to ask Little Q yet another question: Given two sequences $g, h$ of length $n$, find $f$ such that $f_n=\sum\limits_{k=0}^{n}k^ng_kh_{n-k}$. Little Q said to Little K: You are such a newbie. Isn’t this just an easy convolution? What did you learn FFT for? Then he took a careful look and was stunned, realizing he could not solve this problem. To totally defeat Little K, you need to tell him how to handle $4$ special cases. # Background Little Q is a genius and especially likes polynomials. One day, Little K asked a question: Given two sequences $g, h$ of length $n$, find $f$ such that $f_n=\sum\limits_{k=0}^{n}g_kh_{n-k}$. Little Q said to Little K: You are such a newbie. Isn’t this just an easy convolution? What did you learn FFT for? Then Little K spent a month learning FFT and NTT, and went to ask Little Q another question: Given two sequences $g, h$ of length $n$, find $f$ such that $f_n=\sum\limits_{k=0}^{n}\binom{n}{k}g_kh_{n-k}$. Little Q said to Little K: You are such a newbie. Isn’t this just an easy convolution? What did you learn FFT for? Then Little K spent another month learning FFT and NTT, and went to ask Little Q yet another question: Given two sequences $g, h$ of length $n$, find $f$ such that $f_n=\sum\limits_{k=0}^{n}k^ng_kh_{n-k}$. Little Q said to Little K: You are such a newbie. Isn’t this just an easy convolution? What did you learn FFT for? Then he took a careful look and was stunned, realizing he could not solve this problem. To totally defeat Little K, you need to tell him how to handle $4$ special cases.

Given specific sequences $g, h$, compute $f_n$ satisfying $f_n=\sum\limits_{k=0}^{n}k^ng_kh_{n-k}$. This problem has five subtasks. The first four subtasks give different forms of $g, h$ and ask you to compute $f_n$. The fifth subtask does not depend on this equation, but it looks similar in form. **Note: all outputs in this problem should be taken modulo $998244353$ ($119\times 2^{23}+1$, a prime).** --- **Subtask 1 (4 pts):** Given an integer $n$, you need to answer $q$ queries. Each query gives an integer $m$. For each query, $g$ and $h$ are as follows ($0\leq k\leq n$): $$g_k=\begin{cases}1,&k

The first line contains an integer $op$, indicating the subtask number. If $op=1$: The second line contains an integer $n$, and the third line contains an integer $q$. Then follow $q$ lines, each containing an integer $m$. If $op\in \{2,3,4,5\}$: The second line contains an integer $q$. Then follow $q$ lines, each containing two integers $n, m$. The meaning of all variables is given in the problem description.

For each query, output one integer per line, indicating the answer.

### Sample Explanation 1 In this sample, you need to solve Subtask 1, with $n=5,\ \ q=2$. In the first query, $m=2$, then (omitting terms whose addend is $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$$ In the second query, $m=3$, then: $$[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$$ ------ ### Sample Explanation 2 In this sample, you need to solve Subtask 2, with $q=2$. In the first query, $n=4,\ \ m=2$, then: $$[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_4=1^4\times g_1h_3+2^4\times g_2h_2=\dfrac{11}{120} $$ After taking modulo $998244353$, $f_4=\dfrac{11}{120}$ equals $440891256$. The second query has constraints that are too large, so no sample explanation is provided. ------ ### Sample Explanation 3 In this sample, you need to solve Subtask 4, with $q=2$. In the first query, $n=4,\ \ m=2$, then: $$[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_4=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 $$ The second query has constraints that are too large, so no sample explanation is provided. --- ### Sample Explanation 4 In this sample, you need to solve Subtask 5, with $q=2$. In the first query, $n=4,\ \ m=2$, enumerate $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} $$ Adding them all up gives $58$. The second query has constraints that are too large, so no sample explanation is provided. --- ### Constraints **This problem uses bundled testdata, and different subtasks have different statements.** | Subtask ID | $q\leq$ | $n\leq$ | $m\leq$ | Points | | :--------: | :------------: | :------------: | :------------: | :----: | | 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 | All inputs are positive integers. Translated by ChatGPT 5