P11617 [PumpkinOI Round 1] Recurrence

>A simple question: what is a recurrence?

Define a recurrence of a sequence $\{a_0 \dots a_{n - 1}\}$ as a sequence $\{r_0\dots r_m\}$ that satisfies: $$\sum_{j = 0} ^ m r_j a_{i - j} = 0, \forall i \ge m$$ $m$ is called the order of this recurrence. In particular, $r_0\neq 0$. You are given the first $n$ terms of an infinite sequence $\{a_i\}$ and a recurrence $\{b_i\}$ of order $n$ for the sequence $\{a_i\}$. Find the sum of all terms of the sequence $\{a_i\}$. Output the answer modulo $998244353$. It can be proven that, for any input under modulo $998244353$, there exists a corresponding sequence in the real-number sense whose sum is convergent.

The first line contains a positive integer $n$. The second line contains $n$ integers, representing the first $n$ terms of the sequence $\{a_i\}$, i.e. $\{a_0 \dots a_{n-1}\}$, under modulo $998244353$. The third line contains $n+1$ integers, representing the recurrence $\{b_0\dots b_n\}$ under modulo $998244353$.

Output one integer on one line, representing the sum of all terms of the sequence $\{a_i\}$ modulo $998244353$. It is guaranteed that the answer can be represented under modulo $998244353$. That is, if the final answer is a fraction $\frac qp$ (it can be proven that the answer must be a rational number), then $p\not\equiv0\pmod {998244353}$ is guaranteed.

**Sample Explanation #1** $499122176\equiv -\frac12\pmod {998244353}$. $\forall i\ge n,a_i-\frac12\times a_{i-1}=0$, i.e. $a_i=\frac12\times a_{i-1}$. So the sequence $\{a_i\}$ is a geometric sequence $1,\frac12,\frac14,\dots$, and its sum converges to $2$. **Sample Explanation #2** $199648870\equiv -0.6\pmod {998244353},99824435\equiv -0.3\pmod {998244353}$. $\forall i\ge n,a_i-0.6\times a_{i-1}-0.3\times a_{i-2}=0$, i.e. $a_i=0.6\times a_{i-1}+0.3\times a_{i-2}$. After calculation, its sum converges to $14$. **This problem uses bundled/dependent subtasks.** For all subtasks, $1\le n\le5\times 10^3$, $0\le a_i,b_i< 998244353$. In particular, $b_0\neq 0$. | Subtask ID | Score | $n\le$ | Depends On | | :-----------: | :-----------: | :-----------: | :-----------: | | $1$ | $30$ | $1$ | None | | $2$ | $30$ | $2$ | $1$ | | $3$ | $40$ | $5\times 10^3$ | $1,2$ | Translated by ChatGPT 5