### bihariforces's blog

By bihariforces, history, 17 months 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

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