Combinatorics Problem
Contest: Educational Codeforces Round 148 (Rated for Div. 2)
Difficulty rating: 2200
Tags: brute force, combinatorics, dp

Recall that the binomial coefficient $$$\binom{x}{y}$$$ is calculated as follows ($$$x$$$ and $$$y$$$ are non-negative integers):

- if $$$x < y$$$, then $$$\binom{x}{y} = 0$$$;
- otherwise, $$$\binom{x}{y} = \frac{x!}{y! \cdot (x-y)!}$$$.

You are given an array $$$a_1, a_2, \dots, a_n$$$ and an integer $$$k$$$. You have to calculate a new array $$$b_1, b_2, \dots, b_n$$$, where

- $$$b_1 = (\binom{1}{k} \cdot a_1) \bmod 998244353$$$;
- $$$b_2 = (\binom{2}{k} \cdot a_1 + \binom{1}{k} \cdot a_2) \bmod 998244353$$$;
- $$$b_3 = (\binom{3}{k} \cdot a_1 + \binom{2}{k} \cdot a_2 + \binom{1}{k} \cdot a_3) \bmod 998244353$$$, and so on.

Formally, $$$b_i = (\sum\limits_{j=1}^{i} \binom{i - j + 1}{k} \cdot a_j) \bmod 998244353$$$.

Note that the array is given in a modified way, and you have to output it in a modified way as well.

Input format:
The only line of the input contains six integers $$$n$$$, $$$a_1$$$, $$$x$$$, $$$y$$$, $$$m$$$ and $$$k$$$ ($$$1 \le n \le 10^7$$$; $$$0 \le a_1, x, y < m$$$; $$$2 \le m \le 998244353$$$; $$$1 \le k \le 5$$$).

The array $$$[a_1, a_2, \dots, a_n]$$$ is generated as follows:

- $$$a_1$$$ is given in the input;
- for $$$2 \le i \le n$$$, $$$a_i = (a_{i-1} \cdot x + y) \bmod m$$$.

Output format:
Since outputting up to $$$10^7$$$ integers might be too slow, you have to do the following:

Let $$$c_i = b_i \cdot i$$$ (without taking modulo $$$998244353$$$ after the multiplication). Print the integer $$$c_1 \oplus c_2 \oplus \dots \oplus c_n$$$, where $$$\oplus$$$ denotes the bitwise XOR operator.

Constraints:
Time limit: 4.0 s
Memory limit: 1024.0 MB

Example input:
5 8 2 3 100 2

Example output:
1283

Editorial:
Unfortunately, it looks like the constraints were insufficient to cut the convolution solutions off. So it's possible to solve this problem using a very fast convolution implementation, but the model approach is different from that.
One of the properties of Pascal's triangle states that $$$\binom{x}{y} = \binom{x-1}{y} + \binom{x-1}{y-1}$$$. Using it, we can rewrite the formula for $$$b_i$$$ as follows:
$$$$$$b_i = (\sum\limits_{j=1}^{i} \binom{i - j + 1}{k} \cdot a_j)$$$$$$
$$$$$$b_i = (\sum\limits_{j=1}^{i} \binom{i-j}{k} \cdot a_j) + (\sum\limits_{j=1}^{i} \binom{i-j}{k-1} \cdot a_j)$$$$$$
Now, the first sum is almost the same as $$$b_i$$$, but with $$$i$$$ decreased by $$$1$$$. So, it is just $$$b_{i-1}$$$.
What does the second sum stand for? It's actually $$$b_{i-1}$$$, but calculated with $$$k-1$$$ instead of $$$k$$$. upd: The only exception is $$$k = 1$$$, for which the last term in the summation has coefficient $$$\binom{0}{0} = 1$$$, that's why it is equal to $$$b_i$$$ calculated with $$$k = 0$$$, not $$$b_{i-1}$$$.
Now, let $$$c_{i,j}$$$ be equal to the value of $$$b_i$$$ if we solve this problem with $$$k = j$$$. The formula transformations we used show us that $$$c_{i,j} = c_{i-1,j} + c_{i-1,j-1}$$$ (upd: When $$$j = 1$$$, the formula is $$$c_{i,j} = c_{i-1,j} + c_{i,j-1}$$$ instead), so we can use dynamic programming to calculate $$$c_{i,k}$$$ in $$$O(nk)$$$. But we need some base values for our dynamic programming. It's quite easy to see that $$$c_{0,j} = 0$$$; but what about $$$c_{i,0}$$$?
$$$$$$c_{i,0} = \sum\limits_{j=1}^{i} \binom{i - j + 1}{0} \cdot a_j$$$$$$
And since $$$\binom{i - j + 1}{0} = 1$$$, then
$$$$$$c_{i,0} = \sum\limits_{j=1}^{i} a_j$$$$$$
So, in order to obtain $$$c_{i,0}$$$, we can just build prefix sums on the array $$$a$$$.
In fact, it's possible to show that transitioning from the $$$j$$$-th layer of dynamic programming to the $$$(j+1)$$$-th is also just applying prefix sums; then the solution would become just replacing $$$a$$$ with prefix sums of $$$a$$$ exactly $$$k+1$$$ times. This observation was not needed to get AC, but it allows us to write a much shorter code.
Solution complexity: $$$O(nk)$$$.