求路过的做过CLRS的神犇看一眼习题11.3-3谢谢


我能知道它是对的、找不到反例;
但是想不出证明方法。
求指导、谢谢:)
Exercise 11.3.3

算法导论 hash 算法

冰D伊安司 9 years, 9 months ago

ql_f3f23b817ac2851d8f7c3df7719892dd_l3.png


 \begin{align*}
\sum_{i=0}^{l-1}{2^{i p}x_i} &\equiv \sum_{i=0}^{l-1}{(2^{i p}x_i \bmod m)} \tag{mod m} \\
&\equiv \sum_{i=0}^{l-1}{(2^{i p} \bmod m)(x_i \bmod m)} \tag{mod m}\\
&\equiv \sum_{i=0}^{l-1}{x_i \bmod m} \tag{mod m, $m=2^p-1$}
\end{align*}

缭乱的祈祷 answered 9 years, 9 months ago

Your Answer