c810: 未知函數
標籤 : Lagrange Interpolation
通過比率 : 40% (2 人 / 5 人 ) (非即時)
評分方式:
Tolerant

最近更新 : 2018-10-30 09:52

內容

現在有個不超過 $\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
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (16%): 1.0s , <1K
公開 測資點#1 (16%): 1.0s , <1M
公開 測資點#2 (17%): 1.0s , <1M
公開 測資點#3 (17%): 1.0s , <1M
公開 測資點#4 (17%): 2.0s , <1M
公開 測資點#5 (17%): 2.0s , <1M
提示 :

$\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}$,無特殊限制。

標籤:
Lagrange Interpolation
出處:
[編輯:
icube (常數爆炸)
]


編號 身分 題目 主題 人氣 發表日期
沒有發現任何「解題報告」