P10116 [LMXOI Round 1] Random

LMX gives HQZ an interesting sequence. To understand LMX’s preferences, HQZ wants to solve the following problem.

Given an initial sequence of length $n$ that is all $0$, we will perform the following operation $q$ times. - Choose any position $t$ and change the number at that position to any integer between $1$ and $k$. That is, in total there are $(nk)^q$ different operation sequences. For each different operation sequence, there is a corresponding resulting sequence. Next, a matching sequence $B$ of length $m$ is given. You need to compute the total number of occurrences of this matching sequence across every resulting sequence. Note that if a resulting sequence contains multiple occurrences of the matching sequence, they should be counted repeatedly. Since the answer is too large, you only need to output the answer modulo $998244353$. **This problem uses a special method to generate the input data.** The generation format is: $x_i=(a \times i+b)\bmod k +1$, where $x_i$ denotes the required number at position $i$ of sequence $B$.

The first line contains four integers $n,m,q,k$, where $m$ is the length of sequence $B$. The second line contains two integers $a,b$.

Output one integer representing the answer.

**Sample Explanation #1** For the following operation sequences, sequence $B$ appears: - $[1,1],[2,2]$ produces the sequence $[1,2,0]$. - $[2,2],[1,1]$ produces the sequence $[1,2,0]$. - $[2,1],[3,2]$ produces the sequence $[0,1,2]$. - $[3,2],[2,1]$ produces the sequence $[0,1,2]$. For $100\%$ of the data, it is guaranteed that $\forall x_i \in B, 1\le x_i\le k$, $0 \le a,b\le 10^9$, and $m\le n$. | Subtask ID | $n,q,k$ | $m$ | Special Property | Score | | :--------: | :------------------: | :----------: | :--------------: | :---: | | Subtask #1 | $\le 10^9$ | $\le 200$ | $q< m$ | $5$ | | Subtask #2 | $\le 4$ | $\le 4$ | None | $10$ | | Subtask #3 | $\le 500$ | $\le 200$ | None | $10$ | | Subtask #4 | $\le 2\times 10^5$ | $\le 200$ | None | $20$ | | Subtask #5 | $\le 10^9$ | $\le 200$ | None | $20$ | | Subtask #6 | $\le 10^9$ | $\le 3\times 10^6$ | None | $35$ | Translated by ChatGPT 5