Hi Codeforces! I need help solving a problem. Here is a link to the condition: https://docs.google.com/drawings/d/1rzn5TzQJxuF1OulPWgNhBr-EVcLYhECCyUqeQsxZdmg/edit?usp=sharing
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3676 |
| 2 | Kevin114514 | 3659 |
| 3 | jiangly | 3640 |
| 4 | turmax | 3450 |
| 5 | tourist | 3408 |
| 6 | strapple | 3360 |
| 7 | Um_nik | 3354 |
| 8 | squareOf105 | 3348 |
| 9 | maroonrk | 3312 |
| 10 | idontwannadothis…e | 3191 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 153 |
| 2 | nik_exists | 151 |
| 3 | maroonrk | 150 |
| 4 | maspy | 149 |
| 5 | AmShZ | 146 |
| 6 | Um_nik | 143 |
| 7 | Errichto | 139 |
| 8 | adamant | 135 |
| 9 | BledDest | 134 |
| 10 | cry | 130 |
Hi Codeforces! I need help solving a problem. Here is a link to the condition: https://docs.google.com/drawings/d/1rzn5TzQJxuF1OulPWgNhBr-EVcLYhECCyUqeQsxZdmg/edit?usp=sharing
| Название |
|---|



можно ссылку на задачу?
Понятно, что в итоговом массиве каждое из чисел $$$a_k$$$ войдет с каким-то неотрицательным коэффициентом. Зафиксируем $$$a_k$$$ и вычислим для каждого элемента итогового массива этот коэффициент.
Пусть $$$dp[i][j]$$$ — коэффициент, с которым элемент $$$a_0$$$ войдет в $$$j$$$-й элемент массива, полученного через $$$i$$$ итераций. Нетрудно понять, что $$$dp[i][j] = dp[i - 1][j] + dp[i][j - 1]$$$. $$$dp[i][0] = dp[i - 1][0]$$$, а $$$dp[0][i] = 1$$$. Теперь $$$i$$$-му элементу результирующего массива нужно прибавить $$$a_0 \cdot dp[k][i]$$$. Теперь проследим, что изменится, когда мы будем считать коэффициенты для $$$a_1$$$. Нетрудно понять, что элементы динамики в каждой строке как бы сдвинутся на $$$1$$$ вправо, а $$$0$$$-й столбец заполнится нулями. Таким образом, если $$$a_0$$$ входит в элемент $$$i$$$ с коэффициентом $$$dp[k][i]$$$, то $$$a_1$$$ будет входить с коэффициентом $$$dp[k][i - 1]$$$, $$$a_2$$$ — с коэффициентом $$$dp[k][i - 2]$$$, и так далее.
Осталось научиться быстро считать $$$dp[k][i]$$$. Для этого можно посмотреть на формулу: $$$dp[k][i] = dp[k - 1][i] + dp[k][i - 1]$$$. Можно заметить, что $$$dp[k][i] = \binom{k+i}{i}$$$ (действительно, $$$\binom{k+i}{i} = \binom{k+i-1}{i} + \binom{k+i-1}{i-1}$$$). То есть нужно научиться считать $$$\binom{k+i}{i}$$$, где $$$k \leq 10^9$$$, а $$$i \leq 2000$$$. Можно посчитать его по определению: $$$\frac{(k+i)(k+i-1) \cdot \ldots \cdot (k + 1)}{i(i-1) \cdot \ldots \cdot 1}$$$. Можно предподсчитать $$$\binom{k+i}{i}$$$ для всех $$$i$$$ суммарно за $$$O(n^2)$$$. (Во всех формулах из-за 0-индексации нужно уменьшить $$$k$$$ на единицу.)
После этого останется по выведенным формулам посчитать ответ. Переберем элемент $$$a_i$$$, после чего добавим в $$$j$$$-й элемент значение $$$a_i$$$, умноженное на нужный биномиальный коэффициент. Не забываем аккуратно считать по модулю. Итого $$$O(n^2)$$$.