P7705 "Wdsr-2.7" Genius ⑨ and a Mathematical Recurrence

Cirno, the ice fairy who lives at Misty Lake, has always been known for her "wisdom". As a senior student at the temple school, Cirno is very familiar with mathematical recurrences. One day, Teacher Keine wanted to test Cirno. So she wrote down a recurrence of length $m$: $$F_t=\sum_{i=1}^m K_i\times F_{t-i} \quad (t> m)$$ Here, $m$ and $\{K_i\}$ are given. However, since the first $m$ terms of the sequence $\{F_i\}$ are not fixed, there may be infinitely many recurrence sequences that satisfy this formula but have different initial $m$ terms. Keine plans to choose $q$ such sequences $F$ to test Cirno's understanding of sequences. More specifically, Keine will tell Cirno the first $m$ terms of some $\{F_i\}$ one by one. Obviously, this determines an infinite sequence $\{F_i\}$. Still, generating so many sequences is not very fun. So Keine creates an answer sequence $\{A_i\}$, with $A_i=0$ initially. Each time a new $\{F_i\}$ is given, Keine asks Cirno to add $F_1,F_2,F_3,\cdots,F_{b-a+1}$ to the terms $A_a,A_{a+1},\cdots,A_{b-1},A_b$ respectively. Of course, Teacher Keine does not want to make things too hard. So for all numbers, you only need to output their values modulo $p$, where $p$ is a given constant. --- Formally, given $n,q,m,p,\{K_1,K_2,\cdots ,K_m\}$. There are $q$ operations. In each operation, a set of $a,b,\{G_1,G_2\cdots G_m\}$ is given. Define the infinite sequence $\{F_i\}$ by: $$F_t=\begin{cases} G_t & t\le m \cr \sum_{i=1}^m K_iF_{t-i} & t>m \end{cases}$$ Then for all $i\in [a,b]$, set $A_i\gets A_i+F_{i-a+1}$. Finally, output the first $n$ terms of $\{A_i\}$ modulo $p$.

- The first line contains four positive integers $n,q,m,p$, with the meanings as described above. - The second line contains $m$ integers $\{K_1,K_2,\cdots ,K_m\}$, representing the coefficients in the recurrence. - The next $q$ lines each contain $2+m$ integers $a,b,\{G_1,G_2,\cdots G_m\}$, describing one operation.

- Output a single line with $n$ integers, the values of $A_i \bmod p$.

#### Sample Explanation For sample $1$: - Initially, $\{A_i\}=\{0,0,0,0,0\}$. - The first step generates $\{F_i\}=\{1,1,2,3,5\}$, and adds it to $A_1,A_2,A_3$. Now $\{A_i\}=\{1,1,2,0,0\}$. - The second step generates $\{F_i\}=\{1,1,2,3,5\}$, and adds it to $A_2,A_3,\cdots ,A_5$. Now $\{A_i\}=\{1,2,3,2,3\}$. - The third step generates $\{F_i\}=\{2,0,2,2,4\}$, and adds it to $A_1,A_2,\cdots ,A_5$. Now $\{A_i\}=\{3,2,5,4,7\}$. For sample $2$, we have neither a great explanation nor enough space, so we cannot write it here. #### Constraints and Notes $$ \def\arraystretch{1.5} \begin{array}{|c|c|c|c|c|}\hline \textbf{Subtask} & \bm{n} & \bm{m} & \bm{q}& \textbf{分值}\cr\hline 1 & n\le 10^4 & m\le 10 & q\le 10^3 & 10 \cr\hline 2 & n\le 10^5 & m=1 & q\le 10^5 & 20\cr\hline 3 & n\le 10^5 & m=2 & q\le 10^5 & 20\cr\hline 4 & \text{无特殊限制} & \text{无特殊限制} & \text{无特殊限制}& 50 \cr\hline \end{array}$$ - For $100\%$ of the testdata: $ 1 \leq n\le 1\times 10^6;1\le q \leq 1.2 \times 10^5;1 \leq m \leq 15;1 \leq K_i,G_i,p \leq 10^8;1\le a\le b\le n$。 Translated by ChatGPT 5