A Random Code Problem
Contest: Educational Codeforces Round 121 (Rated for Div. 2)
Difficulty rating: 2800
Tags: combinatorics, dp, math, number theory, probabilities

You are given an integer array $$$a_0, a_1, \dots, a_{n - 1}$$$, and an integer $$$k$$$. You perform the following code with it:

Your task is to calculate the expected value of the variable ans after performing this code.

Note that the input is generated according to special rules (see the input format section).

Input format:
The only line contains six integers $$$n$$$, $$$a_0$$$, $$$x$$$, $$$y$$$, $$$k$$$ and $$$M$$$ ($$$1 \le n \le 10^7$$$; $$$1 \le a_0, x, y < M \le 998244353$$$; $$$1 \le k \le 17$$$).

The array $$$a$$$ in the input is constructed as follows:

- $$$a_0$$$ is given in the input;
- for every $$$i$$$ from $$$1$$$ to $$$n - 1$$$, the value of $$$a_i$$$ can be calculated as $$$a_i = (a_{i - 1} \cdot x + y) \bmod M$$$.

Output format:
Let the expected value of the variable ans after performing the code be $$$E$$$. It can be shown that $$$E \cdot n^k$$$ is an integer. You have to output this integer modulo $$$998244353$$$.

Constraints:
Time limit: 3.0 s
Memory limit: 512.0 MB

Note:
The array in the first example test is $$$[10, 35, 22]$$$. In the second example, it is $$$[15363, 1418543]$$$.

Example input:
3 10 3 5 13 88

Example output:
382842030

Example input:
2 15363 270880 34698 17 2357023

Example output:
319392398

Editorial:
I think it's easier to approach this problem using combinatorics instead of probability theory methods, so we'll calculate the answer as "the sum of values of ans over all ways to choose the index on each iteration of the loop".
If a number $$$a_{idx}$$$ is chosen on the iteration $$$i$$$ of the loop, then it is reduced to the maximum number divisible by $$$i$$$ that doesn't exceed the initial value. So, if a number is divisible by all integers from $$$1$$$ to $$$k$$$, i. e. divisible by $$$L = LCM(1,2,\dots,k)$$$, it won't be changed in the operation. Furthermore, if $$$\lfloor \frac{a_{idx}}{L} \rfloor = x$$$, then the value of this element won't become less than $$$x \cdot L$$$.
It means that we can interpret each number $$$a_i$$$ as $$$a_i = x \cdot L + y$$$, where $$$x = \lfloor \frac{a_{i}}{L} \rfloor$$$ and $$$y = a_i \bmod L$$$. The part with $$$x \cdot L$$$ will always be added to the variable ans when this element is chosen, so let's add $$$k \cdot n^{k-1} \cdot x \cdot L$$$ to the answer (which is the contribution of $$$x \cdot L$$$ over all ways to choose the indices in the operations), and work with $$$a_i \bmod L$$$ instead of $$$a_i$$$.
Now all elements of the array are less than $$$L$$$. We can use this constraint by writing the following dynamic programming to solve the problem: $$$dp_{i,j}$$$ is the number of appearances of the integer $$$i$$$ in the array $$$a$$$ over all ways to choose the indices for the first $$$j$$$ iterations.
For $$$j = 0$$$, $$$dp$$$ is just the number of occurrences of each integer in the array $$$a$$$. The transitions from $$$dp_{i,j}$$$ are the following ones:
• if this element is chosen in the operation, then it becomes $$$i' = i - (i \bmod (j + 1))$$$, and we transition to the state $$$dp_{i',j+1}$$$;
• otherwise, the element is unchanged, and we transition to the state $$$dp_{i,j+1}$$$, multiplying the current value by $$$n-1$$$, which is the number of ways to choose some other element in the operation.
How can we use this dynamic programming to get the answer? On the $$$(j+1)$$$-th iteration, the number of times we choose the integer $$$i$$$ is exactly $$$dp_{i,j}$$$, and the number of ways to use the integers in the next operations is $$$n^{k-j-1}$$$, so we add $$$i \cdot dp_{i,j} \cdot n^{k-j-1}$$$ to the answer for every such state $$$dp_{i,j}$$$.
This solution runs in time $$$O(n + LCM(1,2,\dots,k) \cdot k)$$$, which may be too slow if not implemented carefully. Fortunately, we have an easy way to optimize it: use $$$L = LCM(1,2,\dots,k-1)$$$ instead of $$$L = LCM(1,2,\dots,k)$$$, which divides $$$L$$$ by $$$17$$$ in the worst case scenario for our solution. We can do this because even if an integer is changed on the $$$k$$$-th operation, we are not interested in this change since this is the last operation.