Mail.Ru Cup 2018 Раунд 1 |
---|
Закончено |
Вам даны два массива $$$a_0, a_1, \ldots, a_{n - 1}$$$ и $$$b_0, b_1, \ldots, b_{m-1}$$$, и целое число $$$c$$$.
Вычислите следующую сумму:
$$$$$$\sum_{i=0}^{n-1} \sum_{j=0}^{m-1} a_i b_j c^{i^2\,j^3}$$$$$$
Так как это число может быть ну очень большим, выведите его по модулю $$$490019$$$.
Первая строка содержит три целых числа $$$n$$$, $$$m$$$ и $$$c$$$ ($$$1 \le n, m \le 100\,000$$$, $$$1 \le c < 490019$$$).
Следующая строка содержит ровно $$$n$$$ целых чисел $$$a_i$$$ и задаёт массив $$$a$$$ ($$$0 \le a_i \le 1000$$$).
Последняя строка содержит ровно $$$m$$$ целых чисел $$$b_i$$$ и задаёт массив $$$b$$$ ($$$0 \le b_i \le 1000$$$).
Выведите одно число — значение суммы по модулю $$$490019$$$.
2 2 3
0 1
0 1
3
3 4 1
1 1 1
1 1 1 1
12
2 3 3
1 2
3 4 5
65652
В первом примере единственное ненулевое слагаемое соотвествует $$$i = 1$$$, $$$j = 1$$$ и равно $$$1 \cdot 1 \cdot 3^1 = 3$$$.
Во втором примере все слагаемые равны $$$1$$$.
Название |
---|