Skeef79's blog

Prefix sums k times
By Skeef79, history, 3 years ago, translation, In English

Hello codeforces!

I am wondering is there a way to caculate prefix sums $$$k$$$ times modulo $$$p$$$ fast, especially when we can't use matrix multiplication?

By calculating prefix sums $$$k$$$ times I mean this piece of code:

for(int it = 0; it < k; it++) {
    for(int i = 1; i < n; i++)
        pref[i]+= pref[i-1];
}

So if we start with array: $$$1, 0, 0, 0$$$ we will get:

  1. $$$1, 1, 1, 1$$$;

  2. $$$1, 2, 3, 4$$$;

  3. $$$1, 3, 6, 10$$$;

  4. $$$1, 4, 10, 20$$$; ...

  • Vote: I like it
  • +40
  • Vote: I do not like it

»
3 years ago, # |
  Vote: I like it +17 Vote: I do not like it

you have written your blog in russian so the users with the english interface don't see it

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been translated by Skeef79 (original revision, translated revision, compare)

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Fast meaning you want O(n) time independent of the value of k? or what exactly

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Yes, $$$k$$$ can be upto $$$10^{18}$$$, but modulo I think should be around $$$10^5$$$

    → Reply
»
3 years ago, # |
  Vote: I like it +110 Vote: I do not like it

If $$$b$$$ is the array after these operations then $$$b_i = \sum\binom{k+j}{k}a_{i-j}$$$, which is the $$$i$$$-th coefficient of some polynomial product, so this works in $$$O(n\log{n})$$$.

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +22 Vote: I do not like it

    How did you get this formula? Is there any article?

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +77 Vote: I do not like it

      Rotate the second half of your post 45 degrees clockwise and it is Pascal's triangle.

      → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +16 Vote: I do not like it

      Here is some informal handwaving. Each occurrence of $$$a_{i-j}$$$ into $$$b_i$$$ is basically a sequence $$$(d_1, \ldots, d_k)$$$ of nonnegative "steps" with sum being equal to $$$j$$$. It has the following meaning: when we expand the last a[i] := sum(a[0..i]), we look specifically at $$$a_{i-d_1}$$$ from the previous step. During the previous step, this value was assigned the sum of its prefix, but we look only at $$$a_{i-d_1-d_2}$$$, and so on. In the end we will look at $$$a_{i-j}$$$, and this is how it contributed into the final value along this path: through positions $$$(i-j)\to (i-j+d_k)\to\ldots \to i$$$.

      On the other hand, the number of such sequences can be computed using stars and bars technique and equals that binomial coefficient.

      → Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it +21 Vote: I do not like it

we can get k-times prefix sum of an array by a transformation reference. \begin{equation} f_{k} = (\sum_{i=0}^{n-1} a_{i}*x^i)(1/(1-x)^k) \end{equation}

→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it +11 Vote: I do not like it

Btw similar problem exists on project euler 739
Golovanov399 was 4th person to solve it. Its soln is similar to what Golovanov399 mentioned above. If you AC it you would be able to access its discussion forum were people have mentioned how did they solved that problem.

→ Reply
»
3 years ago, # |
  Vote: I like it +24 Vote: I do not like it

Here's the same problem on Codeforces: 223C. Partial Sums

→ Reply