### Skeef79's blog

By Skeef79, history, 3 months ago, translation,

Recently I've come up with this problem:

You are given an array $a_1, a_2, \dots, a_n$ of positive integers.

You need to find $l$, $r$ such that $\frac{\prod_{i=l}^{r} a_i}{r-l+1}$ is maximum over all possible $l,r$ $(l \leq r)$.

Is it possible to solve this faster than $O(n^2)$? This problem looks like something well-known, but I am not sure.

• +20

By Skeef79, history, 3 months ago, translation,

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