資料結構›Ch1 演算法基礎
第 29 題/共 57 題
◀ DS 29/57
29. Modular Arithmetic、Polynomial Evaluation
#DS-01-029中Modular ArithmeticPolynomial Evaluation
題組題幹(本題:⑱,共 2 小題)點擊展開

Let p be a prime number and the set Zp={0,1,2,⋯ ,p−1}\mathbb{Z}_p = \{0,1,2,\cdots,p-1\}. We can map a vector a=⟨a0,a1,a2,⋯ ,ak−1⟩a=\langle a_0,a_1,a_2,\cdots,a_{k-1}\rangle into a vector b=⟨b0,b1,b2,⋯ ,bp−1⟩b=\langle b_0,b_1,b_2,\cdots,b_{p-1}\rangle, where p>k>1p>k>1, ai,bi∈Zpa_i,b_i\in\mathbb{Z}_p and bj=∑i=0k−1aiji mod pb_j=\sum_{i=0}^{k-1}a_ij^i \bmod p, for j=0,…,p−1j=0,\ldots,p-1.

Consider 2 distinct vectors a=⟨a0,a1,a2,⋯ ,ak−1⟩a=\langle a_0,a_1,a_2,\cdots,a_{k-1}\rangle, a′=⟨a0′,a1′,a2′,⋯ ,ak−1′⟩a'=\langle a_0',a_1',a_2',\cdots,a_{k-1}'\rangle, ai,ai′∈Zpa_i,a_i'\in\mathbb{Z}_p, for i=0i=0 to k−1k-1. Suppose a is mapped to b and a' to b' as above. Which of the following statements is/are true?

📄 交大113
跳轉到第題
▤完整推導請見《WH 資工筆記 · 資料結構》Ch1 演算法基礎
本章題號 · 21–40 / 57