Блог пользователя Skeef79

Автор Skeef79, история, 3 года назад, По-русски

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$$$; ...

  • Проголосовать: нравится
  • +40
  • Проголосовать: не нравится

»
3 года назад, # |
  Проголосовать: нравится +17 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится +110 Проголосовать: не нравится

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})$$$.

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +22 Проголосовать: не нравится

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

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится +77 Проголосовать: не нравится

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

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится +16 Проголосовать: не нравится

      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.

»
3 года назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

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

»
3 года назад, # |
Rev. 2   Проголосовать: нравится +21 Проголосовать: не нравится

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}

»
3 года назад, # |
Rev. 2   Проголосовать: нравится +11 Проголосовать: не нравится

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.

»
3 года назад, # |
  Проголосовать: нравится +24 Проголосовать: не нравится

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