Prefix sums k times
Разница между ru1 и en1, 500 символ(ов) изменены
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$;↵
...↵

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский Skeef79 2021-10-26 17:45:42 500 Initial revision for English translation
ru1 Русский Skeef79 2021-10-26 17:41:50 500 Первая редакция (опубликовано)