Chocolates

Practice

2 (7 votes)

Arrays

Linear algebra

Implementation

Fast fourier transform

Combinatorics

Fourier transformations

Modular exponentiation

Mathematics

Modulo arithmetic

Math

Problem

75% Success 686 Attempts 50 Points 3s Time Limit 256MB Memory 1024 KB Max Code

Today is a morning of the $$1^{st}$$ day and you have $$N$$ boxes in a line. The $$i^{th}$$ box from left has $$A_i$$ chocolates. Every night, the number of chocolates in each box increases by an amount equal to the total number of chocolates that were present in the morning in the boxes to the right of it. You need to print the number of chocolates in each box on the morning of $$M^{th}$$ day. The number of chocolates can be very huge, you need to output it modulo $$998244353$$. You can read about modular arithmetic here. You are given $$T$$ test cases. Input format The first line contains a single integer $$T$$ denoting the number of test cases. The first line of each test case contains two space-separated integers $$N$$ and $$M$$ denoting the number of boxes and the day on which you need to report the chocolates. The second line of each test case contains $$N$$ space-separated integers $$A_1, A_2,..,A_N$$ denoting the number of chocolates in each box. Note that $$1$$ is the leftmost box. Output format For each test case(in a separate line), output $$N$$ space-separated integers in a single line denoting the number of chocolates in each box on the morning of $$M^{th}$$ day. Constraints $$ 1 \le T \le 1000 \\ 1 \le N \le 5 \times 10^5 \\ 1 \le M \le 10^{18} \\ 1 \le A_i < 998244353 \\ \text{Sum of N over all test cases does not exceed } 2 \times 10^6 $$

Sample Input

2
3 3
2 3 5
2 838289192
2 4

Sample Output

23 13 5
358423707 4

Explanation

In the first test case, we have $$N = 3$$, $$A = [2, 3, 5]$$. We need to report chocolates on morning of $$3^{rd}$$ day. On the first night, the array becomes $$[2 + 3 + 5, 3 + 5, 5] = [10, 8, 5]$$, that is chocolates in a particular box increases by amount equal to total number of chocolates that were present in the boxes to the right of it. On second night, the array becomes $$[10 + 8 + 5, 8 + 5, 5] = [23, 13, 5]$$. This would be the required number of chocolates on $$3^{rd}$$ morning.   In the second test case, we have $$N = 2$$, $$A = [2, 4]$$. Clearly on the morning of $$M^{th}$$ day, we would have $$2 + 4 \times (M - 1)$$ chocolates in the first box and $$4$$ chocolates in second box. Therefore array becomes $$[2 + 4 \times 838289191, 4]$$. Since we need to take mod $$998244353$$, we output the array $$[358423707, 4]$$.

Code Editor

You need to be logged in to access the code editor

Please wait while we load the editor

Submissions

Please login to view your submissions

You need to be logged in to access the code editor

Please wait while we load the editor