Epic Convolution
题意翻译
**题意**
给两个长度分别为 $n,m$ 的序列 $A$ 和 $B$,下标从 $0$ 开始,再给一个常数 $c$,求:
$$ \text{ans} =\sum\limits_{i=0}^{n-1}\sum\limits_{j=0}^{m-1}A_iB_jc^{i^2j^3}$$
你需要输出答案对 $490019$ 取模的值。
**数据范围**
$n,m \le 10^5$,$A_i,B_i \le 1000$,$c<490019$
题目描述
You are given two arrays $ a_0, a_1, \ldots, a_{n - 1} $ and $ b_0, b_1, \ldots, b_{m-1} $ , and an integer $ c $ .
Compute the following sum:
$ $$$\sum_{i=0}^{n-1} \sum_{j=0}^{m-1} a_i b_j c^{i^2\,j^3} $ $ </p><p>Since it's value can be really large, print it modulo $ 490019$$$.
输入输出格式
输入格式
First line contains three integers $ n $ , $ m $ and $ c $ ( $ 1 \le n, m \le 100\,000 $ , $ 1 \le c < 490019 $ ).
Next line contains exactly $ n $ integers $ a_i $ and defines the array $ a $ ( $ 0 \le a_i \le 1000 $ ).
Last line contains exactly $ m $ integers $ b_i $ and defines the array $ b $ ( $ 0 \le b_i \le 1000 $ ).
输出格式
Print one integer — value of the sum modulo $ 490019 $ .
输入输出样例
输入样例 #1
2 2 3
0 1
0 1
输出样例 #1
3
输入样例 #2
3 4 1
1 1 1
1 1 1 1
输出样例 #2
12
输入样例 #3
2 3 3
1 2
3 4 5
输出样例 #3
65652
说明
In the first example, the only non-zero summand corresponds to $ i = 1 $ , $ j = 1 $ and is equal to $ 1 \cdot 1 \cdot 3^1 = 3 $ .
In the second example, all summands are equal to $ 1 $ .