0 Judge
Code: 0
藪貓不喜歡太長的題目敘述，考慮質數 $p$ 和兩個正整數 $g$ 和 $N$，保證：
$g^1,g^2,g^3,g^4,\cdots,g^N$ 模 $p$ 的結果均不相同
$g^N$ mod $p = 1$
以及兩個多項式
$P(x)=a_0+a_1x+a_2x^2+a_3x^3+\cdots+a_{N-1}x^{N-1}$
$Q(x)=b_0+b_1x+b_2x^2+b_3x^3+\cdots+b_{N-1}x^{N-1}$
計算 $P(g)Q(g)+P(g^2)Q(g^2)+\cdots+P(g^N)Q(g^N)$ mod $p$ 的結果。
每筆測資有三行輸入：
第一行中有三個數，依序為質數 $p$ 和兩個正整數 $g$ 和 $N$
第二行中有 $N$ 個整數，分別為 $a_0, a_1, a_2, \cdots, a_{N-1}$
第三行中有 $N$ 個整數，分別為 $b_0, b_1, b_2, \cdots, b_{N-1}$
其中，對於所有的 $0 \leq i < N$，都有 $0 \leq a_i, b_i < p$。
輸出一行包含一個整數，代表 $$ P(g)Q(g)+P(g^2)Q(g^2)+\cdots+P(g^N)Q(g^N) $$ 模$p$之後的數
3 2 2
1 2
1 1017 9 8
1 16 3 16 1 6 9 7
3 13 7 10 14 6 7 15對於對稱矩陣 $D=D^T$，向量 $b,c$ ：
$$ (Db)^T(Dc)=b^TD^TDc=b^TD^2c $$
觀察本題中 $D^2$ 的樣子，解答可以小於15行
| 配分 | 限制 |
|---|---|
| 10% | 範例測資 |
| 20% | $N=2^k ,k\leq 10, 0 < g < p \leq 10000$ |
| 30% | $N=2^k ,k\leq 18, 0 < g < p \leq 10000000$ |
| 30% | $N\leq 10^6 , 0 < g < p \leq 10000000$ |
| 時限 | 2000ms |
| 記憶體 | 5120000 bytes |