現在有個不超過 $\color{black}{n}$ 次的整係數多項式 $\color{black}{f(x) = a_0 + a_1x + a_2x^2 + \cdots + a_nx^n}$ ,告訴你 $\color{black}{f(0), f(1), \cdots, f(n - 1), f(n)}$ 的值和任意整數 $\color{black}{k}$,你能推出 $\color{black}{f(k)}$ 的值嗎?
由於函數值可能很大,輸入的 $\color{black}{f(x)}$ 都對 $\color{black}{998244353}$ 取了餘數,所以輸出也應做相同處理。
第一行有兩個正整數 $\color{black}{n, q \space (n \le 100000, q \le 1000)}$ ,代表 $\color{black}{deg(f) \le N}$ 和詢問次數。
第二行為 $\color{black}{f(0) \sim f(n)}$ 除以 $\color{black}{998244353}$ 的餘數。
第三行有 $\color{black}{q}$ 個整數 $\color{black}{k_{1 \sim q} (0 \le k_i \le 10^{18})}$ 為詢問內容。
對於每次詢問,輸出 $\color{black}{f(k)}$ 除以 $\color{black}{998244353}$ 的餘數。
3 6 0 1 8 27 0 1 2 3 4 5
0 1 8 27 64 125
$\color{black}{nq}$ 次模運算是可以的。
測資點 $\color{black}{00}$,$\color{black}{n = 2}$。
測資點 $\color{black}{01}$,$\color{black}{n = q = 200}$。
測資點 $\color{black}{02}$,$\color{black}{n = 2000, k_i = N + i}$。
測資點 $\color{black}{03}$,$\color{black}{n = 2000}$。
測資點 $\color{black}{04}$,$\color{black}{q \le 10}$。
測資點 $\color{black}{05}$,無特殊限制。
編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
沒有發現任何「解題報告」
|