SPOJ.com - Problem OVICUMSUM

OVICUMSUM - A Cumulative Sum Problem

no tags

Given an array a₀ of size n (1 < n < 10⁵). Find the array a_k modulo (7340033)

where a_k = cumulative summation array of the array a_k-1.

Means,

a_k[1] = a_k-1[1]

for i > 1 , a_k[i] = a_k[i-1] + a_k-1[i]

Given k (0 < k < 10⁵)

Can you find the array a_k efficiently?

For example,

If a₀ = {1, 2, 1, 3},

a₁ = {1, 3, 4, 7}

a₂ = {1, 4, 8, 15}

a₃ = {1, 5, 13, 28}

Input

First line will contain two integer n, k (size of the array and k from the problem description)

Following n positive integers separated by spaces denoting array a₀ .

All integers are smaller than 10⁵.

Output

Output n integers of the array a_k with spaces in between.

Example

Input:
4 2
1 2 1 3

Output:
1 4 8 15

Submit solution!

hide comments



	Kata: 2018-12-18 05:25:47 Very interesting. I found it's strange that I solved it with quite slow runtime even with enhanced modular arithmetic, but it turned out I could get rid of a whole log k from my solution (O(n lg n lg k)). That's why I got ~15x runtime reduced. More interesting, my code still have room to improve. Gonna come back later with (hopefully) 0.2s solution.
	pkuzby: 2018-12-14 21:46:52 @Cool Licznik Thanks a lot! Finally solved it! I used a mod p modification of FFT instead of regular FFT, it seems to be more convenient for avoiding computational errors in C/C++. Also, 7340033-1 has lots of factors of 2 so it works well with the FFT algorithm. I used a separate program to pre-compute the mod p unit root to save time. Using the recursive formula for the binomials is necessary, an O(n ln(n) ln(k)) algorithm got a TLE. Learned a lot from this problem! Many thanks!
	Cool Licznik: 2018-12-13 22:56:09 @pkuzby I've used ordinary FFT - on floating points (just remember to enough padding zeros). To avoid overflow you can try long double in CPP. For me single FFT was not passing in Python, so I've split inputs into lower and upper bits (this reduces max value to sqrt(max)) and did FFT/convolutions on those.
	pkuzby: 2018-12-03 01:03:47 @Cool Licznik I tried to use a mod p version of FFT, and since 7340033-1 is a multiple of 2^(20) it looked promising. Then I got stuck on how to express the recursive relation under DFT. I am really curious about this problem, would it be OK to ask for a hint?
	Cool Licznik: 2018-12-02 22:02:37 Not sure what we are expected, but it can be solved using FFT and binomials modulo prime (Fermat's little theorem). Possibly convolution using Karatsuba can fit the time limit (but is that less sorcery?).
	nadstratosfer: 2018-09-29 19:21:00 Just realized that with all the "smart" stuff I've been doing, my solution is still O(n^2). Are we expected to use FFT or similar sorcery here?

Submit solution!

Added by:	Nabil
Date:	2018-09-18
Time limit:	2s
Source limit:	50000B
Memory limit:	1536MB
Cluster:	Cube (Intel G860)
Languages:	All