995 . 巫師的多項式挑戰
TopCoder
Tags
Description
在魔法王國阿爾格利亞，偉大的巫師波里寧（PolyNim）創造了一個強大的多項式咒語：
$$ P(x)=a_0+a_1x+a_2x ^ 2+\cdots+a_nx ^ n $$
為了考驗你對多項式魔法的掌握，他將對你問多個問題。
每個問題中，給定一個整數 $k$，你需要計算多項式 $P(x)$ 在 $x=k$ 處的值。因為計算的結果可能會很大，所以你只需要告訴他結果的後九位，並且，你不需要輸出任何的前導零。
舉例來說，如果計算的結果為 $1,000,000,001$，只需要輸出 $1$ 即可，而如果計算的結果為 $1,000,000,000$，只需要輸出 $0$ 即可。
Input Format
第一行包含一個整數 $n$，表示多項式的次數。
第二行包含 $n+1$ 個整數 $a_0, a_1, \cdots, a_n$，表示多項式的係數。
第三行包含一個整數 $Q$，表示問題的數量。
接下來的 $Q$ 行，每行包含一個整數 $k$，表示該問題要計算的點。
- $0 \leq n \leq 2\cdot 10 ^ 5$
- 對於所有 $0 \leq i \leq n$，$0 \leq a_i \leq 10 ^ 9$
- $a_n \neq 0$
- $1 \leq Q \leq 2\cdot 10 ^ 5$
- 每個問題中，$0 \leq k \leq 10 ^ 9$
- $n\cdot Q \leq 2\cdot 10 ^ 5$
Output Format
對每個問題，輸出一行包含一個整數代表 $P(k)$ 不包含前導零的後九位數。
Sample Input 1
2 1 2 3 3 2 0 10
Sample Output 1
17 1 321
Sample Input 2
0 5 5 20 40 27 33 99
Sample Output 2
5 5 5 5 5
Sample Input 3
7 7 0 2 90 54 66 38 20 4 0 16 20 6
Sample Output 3
7 79357447 252560807 7974367
Hints
Problem Source
Subtasks
| No. | Testdata Range | Score |
|---|