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, 3, 4$$$;
$$$1, 3, 6, 10$$$;
$$$1, 4, 10, 20$$$; ...
you have written your blog in russian so the users with the english interface don't see it
Thank you for mentioning
Auto comment: topic has been translated by Skeef79 (original revision, translated revision, compare)
Fast meaning you want O(n) time independent of the value of k? or what exactly
Yes, $$$k$$$ can be upto $$$10^{18}$$$, but modulo I think should be around $$$10^5$$$
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})$$$.
How did you get this formula? Is there any article?
Rotate the second half of your post 45 degrees clockwise and it is Pascal's triangle.
Really...
Thank you!
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.
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}
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}
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.
Here's the same problem on Codeforces: 223C. Partial Sums