Suppose we're given an array of length N upto 1e6 and we apply prefix sum to the array in place, ie. [a, b, c] becomes [a, a + b, a + b + c], we repeat this K times where K can be upto 1e6.
Can we find the resulting array after K operations faster than O(N*K)?
I have observed each preceding element has some contribution for an element in resulting array, but the coefficient doesn't seem intuitive to derive, can someone help derive how to compute the resulting array?
Finding a particular element of the resulting array, for example, just last element in better than O(N*K) would also suffice, hope someone can help.
Very nice problem!
unrated huh learn binary search instead
nice joke, how about you try to get a color on your name yourself?
saar i know him irl, that's why joke
Could you please give a link to the source it comes from ? (That's a rule to be sure the community doesn't help about on ongoing contest.)
https://cses.fi/problemset/task/1716/
I know this has direct math formula but I want to apply DP to it, I was able to reduce it to O(N*M) but on observation, it's just applying prefix sum repeatedly N times to [1, 0, 0...] of length M, so, I was wondering if we could generalize this for arbitrary array and find a particular element of it. which is the last element in above CSES one.
Consider the OGF form of the array as $$$F(x)=\sum\limits_{i=0}^{\infty}a_ix^i$$$.
For a generating function to do a prefix sum, just multiply it by $$$\sum\limits_{i=0}^{\infty}x^i$$$.
So to do k times prefix sum just multiply by $$$(\sum\limits_{i=0}^{\infty}x^i)^k=\sum\limits_{i=0}^{\infty}\binom{k+i-1}{i}x^i$$$, and then use NTT convolution.