Product sums | Practice Problems

Product sums

★★★★★

2.5

2 votes

Implementation, Linear Algebra, Fast Fourier transform, C++, Fourier Transformations, Optimization, Math

Details

Problem

You are given four integers a, d, K, and N. Consider N numbers, $b_1, b_2, ...\ , b_N$ where $b_i = a + (i - 1) \times d$ . Your task is to evaluate the following sum:

$\sum\limits_{v_1 \geq 0, v_2 \geq 0, .., v_N \geq 0 \\ v_1 + v_2 + .. + v_N = k} \left(\prod\limits_{i=1}^{N} b_i^{v_i}\right)$ for each k = 0, 1, 2,... , K

Since the sum can be very large, you are required to print it modulo $998244353$ .

Note: The sum is over all ordered tuples $(v_1, v_2, ...\ , v_N)$ satisfying $\sum\limits_{i=1}^{N} v_i = k$ .

Input format

The first line contains a single integer T denoting the number of test cases.
The first line of each test case contains four space-separated integers a, d, K, and N.

Output format

For each test case (in a separate line), print K + 1 space-separated integers in a new line denoting the sum for each k = 0, 1, 2, .. ,K. Print the output modulo $998244353$ .

Constraints

$1 \leq T \leq 1000 \\ 1 \leq a, d, N < 998244353 \\ 1 \leq K \leq 5 \times 10^5 \\ \text{Sum of K over all test cases does not exceed } 10^6$

Sample Input

2
1 3 3 3
2 1 2 4

Sample Output

1 12 105 820
1 14 125

Time Limit: 5

Memory Limit: 256

Source Limit:

Explanation

In the first test case we have, $a = 1, d = 3, K = 3, N = 3$ . Therefore, $b_1 = 1, b_2 = 4, b_3 = 7$ . We need to sum over tuples of the form $(v_1, v_2, v_3)$ satisfying $\sum\limits_{i=1}^{N} v_i = k$ .

For $k = 0$ , we have only 1 tuple $(0, 0, 0)$ , and the sum is $1$ .
For $k = 1$ , we have 3 possible tuples : $(1, 0, 0), (0, 1, 0), (0, 0, 1)$ . The sum comes out to be $b_1 + b_2 + b_3 = 1 + 4 + 7 = 12$ .
For $k = 2$ , we have 6 possible tuples : $(2, 0, 0), (0, 2, 0), (0, 0, 2), (1, 1, 0), (1, 0, 1), (0, 1, 1)$ . The sum comes out to be $b_1^2 + b_2^2 + b_3^2 + b_1 * b_2 + b_2*b_3 + b_1 * b_3 = 1 + 16 + 49 + 4 + 28 + 7 = 105$ .
For $k = 3$ , we have 10 possible tuples : $(3, 0, 0), (0, 3, 0), (0, 0, 3), (1, 2, 0), (2, 1, 0), (0, 1, 2),$ $(0, 2, 1), (1, 0, 2), (2, 0, 1), (1, 1, 1)$ . The sum comes out to be $b_1^3 + b_2^3 + b_3^3 + b_1 * b_2^2 + b_1^2 * b_2 + b_2 * b_3^2 + b_2 ^2 * b_3 + b_1 * b_3^2 + b_1^2 * b_3 + b_1 * b_2 * b_3 = 820$ .
Note that we output answers in a single line.

In the second test case we have, $a = 2, d = 1, K = 2, N = 4$ . Therefore, $b_1 = 2, b_2 = 3, b_3 = 4, b_4 = 5$ . We need to sum over tuples of the form $(v_1, v_2, v_3, v_4)$ satisfying $\sum\limits_{i=1}^{N} v_i = k$ .

For $k = 0$ , we have only 1 tuple $(0, 0, 0)$ , and the sum is $1$ .
For $k = 1$ , we have 4 possible tuples : $(1, 0, 0, 0), (0, 1, 0, 0), (0, 0, 1, 0), (0, 0, 0, 1)$ . The sum comes out to be $b_1 + b_2 + b_3 + b_4 = 2 + 3 + 4 + 5= 14$ .
For $k = 2$ , we have 8 possible tuples. The sum comes out to be $b_1^2 + b_2^2 + b_3^2 + b_4^2 + b_1 * b_2 + b_2*b_3 + b_1 * b_3 + b_1*b_4 + b_2*b_4 + b_3*b_4 = 125$ .
Note that we output answers in a single line.

Contributers:

Samarth Gupta

Arpa PoorAkhavan