### bihariforces's blog

By bihariforces, history, 7 weeks ago,

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.

• +9

 » 7 weeks ago, # |   0 Very nice problem!
 » 7 weeks ago, # |   0 unrated huh learn binary search instead
•  » » 7 weeks ago, # ^ |   0 nice joke, how about you try to get a color on your name yourself?
•  » » » 7 weeks ago, # ^ |   +1 saar i know him irl, that's why joke
 » 7 weeks ago, # |   0 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.)
•  » » 7 weeks ago, # ^ | ← Rev. 2 →   +5 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.
 » 7 weeks ago, # | ← Rev. 5 →   +14 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.